Time Complexity of For Loops

In our previous blog we learned about basics of time/space complexity using Big O. If you have not checked out my blog I would recommend to do this before you learn about time complexity of for loops:

What is Big O?

Time complexity of dynamic statements

In last blog we learned that to calculate time complexity of dynamic statement we have to consider following things:

  • number of iterations * static statements

Loops are considered as dynamic if they depend on input size  otherwise they are static statements, everything within a loop is considered as static statement. Each static statement is considered as 1 unit of time. To calculate overall complexity of loop:

  • find number of iterations it makes * number of static statements (1 unit each)

Consider following simple example: 

for(i=0; i<n; i++) {
   statements;
}

So loop is considered as single statement whatever falls within a loop if they are static statements then we take 1 unit of time for each static statements. A static statement do not depend on any input size so they are easy to identify:

For loop might have following things inside:

  • static statements - those statement that do not depend on any input
  • dynamic statements - statement that depends on input size

Static Loop Example: 

// this loop makes 5 iterations
// no matter how many times you run
for(i=0; i<5; i++) {
   statements;
}

Dynamic Loop Example: 

// this loop depends on input n
// if you change the value of n
// it will affect time it takes to
// run the entire loop and statements within them
for(i=0; i<n; i++) {
   statements;
}

Calculate Time Complexities of following loops:

To calculate overall time complexity of a loop use following criterias:

  • Write overall equation
  • Find out number of iterations it takes to complete
  • Find out number of statements it has to run within a loop

Example-1:

Consider following simple example where we have single for loop with 1 static statement within it: Formula to calculate overall complexity of a loop is:

  • sum of (number of iterations * (number of static statements or dynamic statements)) 
for(i=0; i<n; i++) { // loops takes n iteration to finish
   statements;  // consider 1 unit of time for static statement
}

Overall Compexity:
------------------
Big(O) = n * 1 
       = n (ignoring 1 because it is considered as constant)
       = O(n)

Example-2:

Let's take another example, consider following program and find out it's overall complexity: 

for(i=0; i<n; i++) { // loops takes n iteration to finish
   statements;  // consider 1 unit of time for static statement
}

for(j=0; j<n; j++) { // loops takes n iteration to finish
   statements;  // consider 1 unit of time for static statement
}

In above example we have two loops which runs one by one when you execute the entire program. To find overall complexity of your program it is sum of all statements within a program. 

Big (O) = Statement 1 + Statement 2
        = Complexity of Loop 1 + Complexity of Loop 2
        = n + n
        = 2n (ignore the constant)
        = O(n) -> consider only higher term

Example-3:

Let's move to bit more complex code and try to figure out complexity of following program: 

for(let i = 1; i <= n; i++) {    // n - iterations
  for(let i = 1; i <= 5; i++) {  // 5 - iterations
    console.log(i);              // 1 - time unit (static statement)
  }
}

Alright now we have loop within a loop, however we know that if loop depends on input size it is considered as dynamic otherwise it is a static statement. Our first loop is dynamic in nature, the loop inside is a static in nature.

For the second loop no wonder how many times you run your top loop it will always repeat for 5 times therefore it is considered as a static statement which has 1 unit of time.

For all static statements we consider 1 unit of time. 

for(let i = 1; i <= n; i++) {    // n - iterations (n)
  for(let i = 1; i <= 5; i++) {  // 5 - iterations (static statement) (1)
    console.log(i);              // 1 - static statement (1)
  }
}

Overall Complexity:
O(n) = n * 1 * 1
     = O(n) -> ignoring all constants

Example-4:

Moving onto more advance loop find out time complexity of following program: 

for(let j = 1; j <= n; j++) {      // dynamic statement - n iterations
  for(let i = 1; i <= n; i*=3) {   // dynamic statement - n iterations
      console.log(i, j);           // static statement - 1 unit of time
  }
}

// Overall Complexity would be:
Big (O) = n * n * 1
        = n^2
        = O(n^2)

Example-5:

Find time complexity of following program: 

for(let i = 0; i < n; i++) {         // dynamic - n reps
  for(let j = 0; j < n; j++) {       // dynamic - n reps
     for(let k = 0; k < n; k++) {    // dynamic - n reps
        console.log(i, j, k);        // statuc - 1 unit
     }
  }
}

// Overall Complexity would be:
Big (O) = n * n * n * 1
        = n^3
        = O(n^3)

Other Examples: 

// O(n) complexity
for (var i=0; i<n; i++) {   // n iterations
    console.log(i);
}  

// O(n^2) complexity
for (var i=0; i<n*n; i++) { // n*n iterations
    console.log(i);
}  

// O(n^3) complexity
for (var i=0; i<n*n*n; i++) { // n*n*n iterations
    console.log(i);
}

I hope you enjoyed this tutorial on finding time comeplexity of different types of loops. Stay tune for my new articles on Big O.

Next, read about what is constant time complexity and how you can calculate it:

Constant Time Complexity

↑