Solution #

The code for this challenge is reproduced below:

C++

int main(){
  int n =10;   
  int sum = 0; 
  int var = 1;  
  float pie = 3.14;
  
  while (var < n){   // O(log3 n)
    cout << pie << endl;   // O(log3 n)
    for (int j = 1; j < n; j+=2){   // O((log3 n)*(n/2)) 
      sum+=1;   // O((log3 n)*(n/2))
    }
    var*=3;    // O(log3 n)
  }
  cout << sum << endl;
}

Time Complexity

The outer loop in this problem runs $log_3(n)$ times since var will first be equal to $1$ , then $3$ , then 6, then $9,\cdots$ , until it is $3^k$ such that $3^k < n$ . In the inner loop, int j=1; runs $log_3(n)$ times, j<n gets executed $log_3(n)\times(\frac{n}{2}+1)$ times and j+=2 executed $log_3(n)\times\frac{n}{2}$ times. The sum+=1; line also runs a total of $log_3(n)\times\frac{n}{2}$ ...

1.Introduction to Complexity Measures

2.Introduction to Arrays

3.Introduction to Linked Lists

4.Introduction to Stack/Queues

5.Introduction to Graphs

6.Introduction to Trees

7.Trie

8.Introduction to Heap

9.Introduction to Hashing

10.Summary of Data Structures

Mock Interview

Solution: Nested Loop with Multiplication (Basic)

Solution #

Time Complexity