Analysis of loop in Programming

Loop is a fundamental problem-solving operation in programming. A lot of coding problem solutions involve various kinds of loop structures. Moreover, some problem-solving approaches are purely based on loop—building partial solutions using a single loop, two-pointers approach, sliding window approach, BFS traversal, bottom-up approach of dynamic programming, problem-solving using stack, etc. So the efficiency of such an algorithm depends on the loop structure and operations inside the loop.

These two loop patterns appear frequently in our solutions:

  • Single loop: loop running constant time, a loop is running n times, loop growing exponentially, a loop running based on the specific condition, a loop running with data structure, consecutive single loops, etc.
  • Nested loops: two nested loops, three nested loops, single loop with nested loops

One idea would be simple: to design a better algorithm or optimize the code further, we should learn to analyze the time complexity of the loop in terms of Big-O notation. Learning time complexity analysis of loops is not difficult. After some basic practice of various loop patterns, we can make optimization decisions quickly and save a lot of analysis time.

Steps to analyse the time complexity of the loop

  • Counting the total loop iteration in the worst case — we can get this insight from considering the worst-case scenario, initial and final value of the loop variable, loop condition, and increment or decrement operation. Most of the time loop will be running for each data element or total input size.
  • Calculating the time complexity of the code in the loop body— loop execute this code on each iteration to get the final result. This code may contain conditional statements, comparison operation, swapping operation, assignment operation, etc.
  • The time complexity of loop = (count of loop iterations in the worst case) * (time complexity of the code in the loop body). We represent this in the form of Big-O notation by ignoring lower-order terms and coefficients.

Sometimes, we can also follow another simple approach:

  • Identify the most critical operation inside the loop, which executes the maximum number of times in the worst case. This critical operation would be the dominating factor in the time complexity function.
  • Now calculate the total count of this operation for the complete loop in terms of input size. Representing this expression in terms of Big-O notation will give the time complexity of the loop.

Let’s analyze the time complexity of the various loop pattern.

Time complexity analysis of a single loop

A loop running constant times: O(1)

for (int i = 1; i <= c; i = i + 1) 
{  
    some O(1) expressions
}

Here loop is running constant times and performing O(1) operation at each iteration of the loop. Time complexity = c*O(1) = O(1)*O(1) = O(1)

A loop running n times and incrementing/decrementing by a constant: O(n)

//example 1
for (int i = 1; i <= n; i = i + c) 
{  
    some O(1) expressions
}

//example 2
for (int i = n; i > 0; i = i - c) 
{
    some O(1) expressions
}

Here both loops are running some n times and performing O(1) operation at each iteration of the loop. Time complexity = n*O(1) = O(n)*O(1) = O(n)

A loop running constant multiple of n times: O(n)

for (int i = 1; i <= 3*n; i = i + 1) 
{
    some O(1) expressions
}

Here loop is running some cn times and performing O(1) operation at each iteration of the loop. Time complexity = cn*O(1) = O(n)*O(1) = O(n)

Two pointers loop: O(n)

l = 0, r = n - 1
while (l <= r) 
{
    if (condition) 
    {
        some O(1) expressions
        l = l + 1
    }    
    else 
    {
        some O(1) expressions
        r = r - 1
    }
    some O(1) expressions
}

In the above loop, based on some conditions, we are either incrementing l or decrementing r by one and performing an O(1) operation at each step of the iteration. Loop will run n times because l and r are starting from opposite ends and end when l > r. So time complexity = n*O(1) = O(n)

A loop incrementing/decrementing by a constant factor: O(logn)

//example 1
for (int i = 0; i < n; i = i*2) 
{
    some O(1) expressions
}

//example 2
for (int i = n; i > 0; i = i/2) 
{
    some O(1) expressions
}

Here loop is running in the range of 1 to n, and the loop variable increases or decreases by a factor of 2 at each step. Thus, we need to count the total number of iterations performed by the loop to calculate the time complexity. Let’s assume the loop will terminate after k steps where the loop variable increases or decreases by a factor of 2. Then 2^k must be equal to the n i.e. 2^k = n and k = logn = O(logn).

So loop will run O(logn) number of times and doing O(1) operation at each step. Time complexity = k * O(1) = O(logn)* O(1) = O(logn)

Loop incrementing by some constant power: O(log(logn))

// Here c is a constant greater than 1   
for (int i = 2; i < = n; i = pow(i, c)) 
{ 
    some O(1) expressions
}

Here, the loop is running in the range of 1 to n, but the loop variable increases by factor i power constant c. So how do we calculate the total number of loop steps? Let’s think!

  • The first iteration of the loop is starting with i = 2.
  • At second iteration, value of i = 2^c.
  • At third iteration, value of i = (2^c)^c = 2^(c²)
  • And it will go so on till end. At any ith iteration the value of i = 2^(c^i)
  • Loop will end when 2^(c^i) = n
2^(c^i) = n
Let's take log of base 2 from both sides.
=> log2(2^(c^i)) = log2(n)
=> c^i = logn

Again take log of base c from both sides.
=> logc(c^i) = logc(logn)
=> i = logc(logn)
=> i = O(log(logn))

So loop will run logc(log(n)) number of times, where each iteration is taking O(1) time. So the overall time complexity = O(log(log(n))) * O(1) = O(log(log(n)))

Consecutive single loops: O(m + n)

for (int i = o; i < m; i = i + 1) 
{  
    some O(1) expressions
}
for (int i = 0; i < n; i = i + 1) 
{
    some O(1) expressions
}

For calculating such consecutive loops, we need to do the sum of the time complexities of each loop. So overall time complexity = Time complexity of loop 1 + Time complexity of loop 2 = O(m) + O(n) = O(m + n)

Time complexity analysis of the nested loops

The time complexity of nested loops is equal to the number of times the innermost statement is executed.

Two nested loops: O(n²)

for (int i = 0; i < n; i = i + 1) 
{
    for (int j = 0; j < n; j = j + 1) 
    {
          some O(1) expressions
    }
}

In the above nested-loop example, the inner loop is running n times for every iteration of the outer loop. So total number of nested loop iteration = total number of iteration of outer loop total number of iteration of inner loop = n * n = n² = O(n²).

At each step of the iteration, the nested loop is doing an O(1) operation. So overall time complexity = O(n²) * O(1) = O(n²)

for (int i = 0; i < n; i = i + 1) 
{
    for (int j = i + 1; j < n; j = j + 1) 
    {
        some O(1) expressions
    }
}

In the above nested loop example, outer loop is running n times and for every iteration of the outer loop, inner loop is running (n — i) times. So total number of nested loop iteration = (n-1) + (n-2) + (n-3)…..+ 2 + 1 = sum of arithmatic series from i = 0 to n-1 = n(n-1)/2 = n²/2 — n/2 = O(n²) At each step of the iteration, the nested loop is doing an O(1) operation. So overall time complexity = O(n²) * O(1) = O(n²)

Note: it’s an exercise for you to analyze the following loop.

for (int i = 0; i < n; i = i + 1) 
{
    int j = i
    while (j > 0) 
    {
        some O(1) expressions
        j = j - 1
    }
}

Combination of single and nested loops

We need to do the sum of the time complexities of each loop. In such a case, the time complexity is dominated by the time complexity of the nested loop.

for (int i = 0; i < n; i = i + 1) 
{
    some O(1) expressions
}

for (int i = 0; i < n; i = i + 1) 
{
    for (int j = 0; j < m; j = j + 1) 
    {
        some O(1) expressions
    }
}

for (int k = 0; k < n; k = k + 1) 
{
    some O(1) expressions
}

So, time complexity = Time complexity of loop 1 + Time complexity of loop 2 + Time complexity of loop 3 = O(n) + O(mn) + O(n) = O(mn)

Three nested loops: O(n³)

for (int i = 0; i < m; i = i + 1) 
{
    for (int j = 0; j < n; j  = j + 1) 
    {
        for (int k = 0; k < n; k  = k + 1)
        {
            some O(1) expressions
        }    
    }
}

All three nested loops are running n times and doing O(1) operation at each iteration, so time complexity = n * n * n*O(1) = n³ * O(1) = O(n³)*O(1) = O(n³)

for(int i = 1; i < n; i = i + 1) 
{   
    for(int j = i + 1; j <= n; j  = j + 1) 
    {
        for(k = i; k <= j; k  = k + 1) 
        {
            some O(1) expressions
        }
    }
}

In the above three nested loop situations, the outer loop runs n - 1 time, but two inner loops run n - i and j -i + 1 time. So what would be the total count of the nested loop iterations? Let’s think.

       n - 1     n        j
T(n) =   ∑       ∑        ∑    O(1)
       i = 1  j = i + 1  k = i

Now we solve this tripple summation by expanding the summation one by one.

Higher-order term in T(n) is n^3, then T(n) = O(n^3). We are ignoring lower-order terms and coefficients.

Enjoy learning, Enjoy coding, Enjoy algorithms!

Our Weekly Newsletter

Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!

We Welcome Doubts and Feedback!

More Content From EnjoyAlgorithms