Time Complexity calculation of iterative programs

4 min readDec 31, 2019

The time complexity of an algorithm estimates how much time the algorithm will use for some input.

Let’s take an example to explain the time complexity.

Imagine a street of 20 book stores. Now, one of your friend suggested a book that you don’t have. Here are some ways to find the book from book stores.

O(1): You go and visit the first book store, if it has the book. If you find the book in the first store it self then the time complexity would be O(1).

O(log n): You divide the book stores into two groups, then ask: “Is it on the left side, or the right side of the bookstores?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one book store which has book you needed. This is what you mean by O(log n).

O(n): You go and visit the first book store, if it’s not available then 2nd,3rd and so on..till the last book store.In this case the time complexity would be O(n).

So, finally the best case for this problem is finding the book at very first store, average case is dividing the book stores into two and search and the worst case is go and visit each store

Calculation rules:

Loops:

The time complexity of an algorithm is denoted O (Big oh).

A common reason why an algorithm is slow is that it contains many loops that go through the input. The more nested loops the algorithm contains, the slower it is.

If there are k nested loops, the time complexity is O ( n^k ).

Example 1:

k = 1 means single loop

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

time complexity is O(n^k) . Here k is 1, so the solution would be O(n¹).

Time complexity: O ( n )

Example 2:

k = 2 means loop inside the loop

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j++) {
       // code
   }
}

the time complexity of the above code is O(n^k). Here k is 2. So the solution would be (n²).

Time complexity: O( n² )

Example 3:

k = 3 means length of nested loop is 3

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {        for (int k = 1; k <=n; k++){            //code         }
    }
}

the time complexity of the above code is O(n^k). Here k is 3. So the solution would be (n³).

Order of magnitude

A time complexity does not tell us the exact number of times the code inside a loop is executed, but it only shows the order of magnitude. In the following examples, the code inside the loop is executed 3 n , n + 5 and n /2 times, but the time complexity of each code is O ( n ).

Example 1:

for (int i = 1; i <= 3*n; i++) {
 // code
}

Example 2:

for (int i = 1; i <= n+5; i++) {
 // code
}

Example 3:

for (int i = 1; i <= n; i += 2) {
 // code
}

As another example, the time complexity of the following code is O ( n² ):

for (int i = 1; i <= n; i++) {
   for (int j = i+1; j <= n; j++) {
      // code
   }
}

and one more example, the time complexity of the following code is O(M×N)

for (int i = 1; i <= m; i++) {
   for (int j = 1; j <= n; j++) {
      // code
   }
}

Phases:

If the algorithm consists of consecutive phases, the total time complexity is the
largest time complexity of a single phase. The reason for this is that the slowest

phase is usually the bottleneck of the code.

For example, the following code consists of three phases with time complexities

O ( n ), O ( n² ) and O ( n ). Thus, the total time complexity is O ( n² ).

public static void main(String args[]){  //Phase 1, time complexity is O(n)     for (int i = 1; i <= n; i++) {
          // code
     }  //Phase 2 , time complexity is O(n²)     for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= n; j++) {
              // code
          }
     }  //Phase 3, time complexity is O(n)    for (int i = 1; i <= n; i++) {
             // code
    }}

Time Complexity is phase1 + phase 2 + phase 3 time complexities

that means O(n) + O(n²) + O(n), here phase 2 taken highest time to execute

So, Our time complexity would be (n²).

Order of growth:

Thank you all.