Finding Time Complexity (Asymptotic Analysis)

There are some basic code statements that are used to build complete program. It is necessary to know their time complexities in order to calculate the time complexity of whole code/algorithm.

We will look at them one by one-

1. Constant Time [O(1)]

1
2
3
4
5
6

void sum() {
int a= 2;
int b=3;
int c = a + b;
System.out.println(c);
}

In above code we are not taking any input. So this code is independent of input size. Lets say the above code takes time C to execute. This time will always be constant irrespective of the input size. In asymptotic analysis we say that the time complexity is O(1).

2. Simple Loops

1
2
3
4
5
6

int k= 0;//time c1 
// loop will execute n times 
for(int i = 1 ; i<=n ; i++)
 {
 k= k+ i; //time C2 
}

Total time = Time taken by initialization statement  + Time taken by statements inside loop x Number of time loop will execute
Total time = C1 + C2 x n
Total time = C1 + C2n i.e. O(n)

3. Nested Loops

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int k= 0, m = n; //time C1

// outer loop will execute n times
  for(int i = 1 ; i<=n ; i++) {

   k= k+ i; //time C2

// inner loop will also execute n times
for(int j = n ; j>=1 ; j--) {

   m= m- j; //time C3
    
}
}

In nested loops we analyze time from inside out. 

Time taken by inner loop = C3 x n

Total time  = Time taken by initialization statement + Time taken by statements inside outer loop x Number of time outer loop will execute
Total time = C1 + (C2 + C3n) x n
Total time = C1 + C2n + C3n²   time  i.e. O(n²) 

4. Consecutive Statements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int x = 0, k=0; //time C1

// loop will execute n times
  for(int y = 1 ; y<=n ; y++) {

   x= x+ y; //time C2
     
}

// outer loop will execute n times
  for(int i = 1 ; i<=n ; i++) {

   k= k+ i; //time C3

// inner loop will also execute n times
for(int j = n ; j>=1 ; j--) {

   m= m- j; //time C4
     
}
}

Total time =  C1 + C2n + (C3 + C4n) x n
Total time =  C1 + C2n + C3n + C4n² 
i.e. O(n²) 

5. If else statements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

boolean bool; //time C1

if(bool) {
  return true; //time C2
  
}
else {

// loop will execute n times
  for(int y = 1 ; y<=n ; y++) {

    y++; //time C3
     
}

}

Here we check for worst case scenario
(remember general rules? ) i.e. what will be the larger time complexity?

Total time will be either C1 + C2 in case 'if' condition is true. Or it will be C3n in case else statement executes. So, maximum time complexity in worst case would be O(n).

6. Logarithmic

1
2
3
4
5

 for(int i = 1 ; i<=n ; i++) {

   i= i*2; //time C

}

Here value of i is becoming twice in every execution and hence reducing the number of times the loop will execute. Let's see how it goes-
Initially i = 1 i.e. 2⁰
Execution 1 -> i = 2 i.e. 2¹
Execution 2 -> i = 4 i.e. 2²

Execution 3 -> i = 8 i.e. 2³

Execution 4 -> i = 16 i.e. 2⁴ and so on...

Lets say 2^k = n. If we take log on both side to the base 2, we get
log2^k = logn
k.log2 = logn
k = logn (since log2 to the base 2 is 1)

k is nothing but the total time taken by loop and hence time complexity is O(logn).