Practice Questions on Time Complexity Analysis in C++

Introduction

Besides solving coding problems, one should be aware of the time complexity of the implemented algorithm so that it can be optimized further if possible.

Time complexity is the running time of an algorithm. Big O-notation is used to express the number of primitive operations executed as a function of input size.

Any algorithm can be classified into some type based on its complexity. See the classes mentioned below.

Here are the special classes of algorithms:

• Logarithmic: O(logn) 
• Linear: O(n) 
• Quadratic: O(n²) 
• Polynomial: O(n^k), k ≥ 1 
• Exponential: O(aⁿ), a > 1
   

Also, have a look at the blog on Asymptotic Notations for a better understanding of the topic.

Also See, kth largest element in an array and Euclid GCD Algorithm

Practice Questions on Time Complexity Analysis in C++

Let us now practice some questions on time complexity analysis and get more familiar with the topic.

Q1: Analyze and find the time complexity of the below function from the code snippet.

for(int i=1;i<=n;i++){
    cout<<i<<endl;
}
for(int j=1;j<=m;j++){
    cout<<j<<endl;
}

Note: first, try to solve the problem and then see the below solution approach.

In the above code, the first loop will run n times and the second loop will run m times So, we can say the time complexity of the above code is O(n+m).

Q2: Analyze and find the time complexity of the below function from the code snippet.

int k=1;
while(k<=n){
	cout<<k<<endl;
	k=k*2;
}

Note: first, try to solve the problem and then see the below solution approach.

In the above code, the while loop will run logn times as k is multiplied by 2 for every iteration. So, we can say the time complexity of the above code is O(logn).

Q3: Analyze and find the time complexity of the below function from the code snippet.

for(int i=n/2;i<=n;i++){
	for(int j=1;j<=n;j=j*2){
   		cout<<i<<j<<endl;
	}
}

Note: first, try to solve the problem and then see the below solution approach.

In the above code, the outer loop will run (n/2) times, and for each value of i, the inner loop will run (logn) times. So, the total number of operations is n/2*logn. We can say the time complexity of the above code is O(n*logn ).

Q4: Analyze and find the time complexity of the below function from the code snippet.

if(i>j){
	j==0? j++ : j--;
}

Note: first, try to solve the problem and then see the solution below.

A Conditional statement takes O(1) time to execute. In the above code, there are only two conditional statements. So, it takes constant time to execute. Then we can conclude the time complexity of the above code is O(1).

Q5: Analyze and find the time complexity of the below function from the code snippet.

for (int i = 0; i < n; i++)
        for (int j = i; j > 0; j--)
            cout << i << j;

Note: first, try to solve the problem and then see the solution below.

In the above code, the outer loop will run (n) times, and for each value of i, the inner loop will run (i) times. So, the total number of operations is n*i, and the maximum value of i will be n, so the overall time complexity of the problem will be n O(n*n).

Read More - Time Complexity of Sorting Algorithms

Must Read Algorithm Types