Tagged
• Algorithm
• Time Complexity
•

# 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 = 011If 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).```

• Algorithm
• Time Complexity
•
...