What is Time Complexity

Time complexity is defined as the amount of time taken by an algorithm to run for a given input. An algorithm consists step by step procedure to solve a given problem, so time complexity of the algorithm measures the time taken to execute each statement of the algorithm.

Lets start with a simple example, given an array contains n integers and an integer x, and given the problem that need to find out whether x present in the array or not.

One simple solution for the problem is, we can traverse the array and can check any element matches with x or not.

1for i : 0 to n-1 
2if a[i] == x 
3     return true 
4return false 

Below are the possibilities :

• If first element of the array matches with x, then it return true. So in this case, only one comparison is needed and so time complexity is O(1).
• If the array does not contain given element x, then after iterating over the array we do return false, so Here we do maximum of n comparisons. So time complexity is O(n).
• As time complexity always matters in worst case , how much time does our algorithm takes, so the time complexity of linear search is O(n).

Below are the some of the problems on time complexity :

Time Complexity Problems

Q1 ) What is the time complexity of the below code

1int a = 0;
2for(int i = 0; i < n; ++i) { 
3    for (int j = n; j > i; j--) { 
4        a = a + i + j;
5    }
6}

1Answer : O(n²)

1Explanation : 
2When i = 0, it runs for n times. 
3When i = 1, it runs for n - 1 times. 
4When i = k, it runs for n - k times 
5
6.
7.
8.
9 
10So, total = n + (n - 1) + (n - 2) + … + 1 + 0  
11          = n * (n + 1) / 2 
12          = O(n²) times. 

Q2 ) What is the time complexity of the below code :

1int a = 0, i = n;
2while (i > 0) {
3    a += i;
4    i /= 2;
5}

1Answer : O(log n)

1Explanation : 
2 
3In every iteration i value gets updated to i/2 
4After Iteration 1, i = i / 2 
5After Iteration 2, i = i / 4 = i / 2² 
6After Iteration 3, i = i / 8 = i / 2³
7.
8.
9.
10After Iteration k, 
11        i =  i / 2ᵏ < 1  or  2ᵏ > n 
12So      k = log n 

Q3 ) What is the time complexity of the below code :

1int i, j = 0;
2
3for(i = 0; i < n; ++i) {
4    while(j < n && a[i] < a[j]) {
5        j++;
6    }
7}

1Answer : O(n)

1Explanation : 
2 
3Inside for loop while loop is getting executed with some condition, but here inner loop condition variable j is not getting initialized every time and based on the other condition check (a[i] < a[j]) the value gets updated 
4 
5If n = 3  
6Iteration 1 : i = 0, j = 0. a[0] < a[0] is false. 
7So, the inner while loop breaks. 
8 
9 
10Iteration 2: i =1, j = 0
11If a[1] < a[0] is false, inner loop breaks and j value is still the same..
12
13If a[1] < a[0] is true. j becomes 1 and then it checks loop condition again and the condition become a[1] < a2 which is false and inner loop breaks 
14
15Iteration 3 :i = 1, j = 1.  => Condition false and inner loop breaks again. 
16or in iteration 2, j value not get changes, then two times it check until j becomes 1. similar way if we continue by assuming a[i+1] < a[i] , 
17
18Iteration 4 : i = 2, j = 1 => a[2] < a[1]. True. j = 2. 
19
20Iteration 5 : i = 2, j = 2  => Condition false. Break.
21
22Iteration 6 : i = 3, j = 2  => a[3] < a[2]. True. j = 3.
23
24Iteration 7 : i = 3, j = 3. Condition false. Break. 
25
26This way even if a[i+1] < a[i] or a[i+1] > a[i] , we execute inner loop n times, so total iterations is 2*n . So time complexity is O(n)

Q4 ) What is the time complexity of the below code :

1for(int i = 0; i < n; i = i+2) {
2    System.out.println("Hello");
3}

1Answer : O(n)

1Explanation : 
2
3For loop maximum value is n and in each iteration we are updating i with i+2.
4So the time complexity of the above code is O(n/2) which is equivalent to O(n).