# Time Complexity Analysis

# 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-12if a[i] == x3 return true4return 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 times56.7.8.910So, total = n + (n - 1) + (n - 2) + … + 1 + 011 = n * (n + 1) / 212 = 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 :23In every iteration i value gets updated to i/24After Iteration 1, i = i / 25After 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ᵏ > n12So k = log n

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

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

1Answer : O(n)

1Explanation :23Inside 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 updated45If n = 36Iteration 1 : i = 0, j = 0. a[0] < a[0] is false.7So, the inner while loop breaks.8910Iteration 2: i =1, j = 011If a[1] < a[0] is false, inner loop breaks and j value is still the same..1213If 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 breaks1415Iteration 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] ,1718Iteration 4 : i = 2, j = 1 => a[2] < a[1]. True. j = 2.1920Iteration 5 : i = 2, j = 2 => Condition false. Break.2122Iteration 6 : i = 3, j = 2 => a[3] < a[2]. True. j = 3.2324Iteration 7 : i = 3, j = 3. Condition false. Break.2526This 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 :23For 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).