Time Complexity Analysis of Loop in Programming
We encounter various loop patterns when solving different coding questions. On the other hand, many problem-solving approaches are based on loops. For example:
- An incremental approach using a single loop
- An incremental approach using nested loops
- Two-pointers approach
- Sliding window approach
- BFS traversal of graphs and trees
- Bottom-up approach in dynamic programming
- Problem-solving using data structures like stacks, queues, hash tables, heaps, etc.
One idea is simple: To design better algorithms or optimize the code further, we should learn to analyze the time complexity of various loop patterns. Once we have good practice, we can confidently think of new solution ideas or make optimization decisions quickly.
The time complexity of a loop pattern depends on various factors like the number of iterations, the cost of operations at each iteration, etc. In most situations, we frequently encounter such loop patterns:
- Single loop patterns: A loop running constant time, a loop running n times, a loop growing exponentially, a loop running based on a condition, a loop running with a data structure, double traversal, etc.
- Nested loops: Two nested loops, three nested loops, a single loop followed by nested loops, etc.
Steps to analyze the time complexity of loop
The time complexity of the loop = (Number of loop iterations in the worst case) * (Time complexity of code executing at each iteration). We can represent this in terms of Big-O notation by ignoring lower-order terms and coefficients.
- Counting total loop iterations in the worst case: We can gain this insight by considering the worst-case input scenario, initial and final value of the loop variable, loop condition, and increment or decrement operations.
- Calculating time complexity of code executing at each iteration: A loop executes some lines of code on each iteration. This code may contain various operations like conditional statements, comparisons, swapping, assignments, shifting, copying, calls to other functions, etc.
Sometimes, we can also follow this approach:
- Identify the most critical operation inside the loop, which executes the maximum number of times in the worst case. This critical operation will be the dominating factor in the time complexity function.
- 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 move forward to analyze various loop patterns.
Analysis of single loop patterns
Loop running constant times: O(1).
for(int i = 1; i <= c; i = i + 1)
{
Some O(1) expressions
}
// while loop version
int i = 1;
while(i <= c)
{
Some O(1) expressions
i = i + 1;
}Here loop is running constant times and performing O(1) operation at each iteration. Time complexity = c * O(1) = O(1) * O(1) = O(1).
Loop running n times and incrementing or decrementing by constant: O(n).
Example 1: Loop incrementing by some constant c.
for(int i = 1; i <= n; i = i + c)
{
Some O(1) expressions
}Example 2: Loop decrementing by some constant c.
for(int i = n; i > 0; i = i - c)
{
Some O(1) expressions
}Here both loops are running n/c times and performing O(1) operation at each iteration. Time complexity = n/c * O(1) = O(n) * O(1) = O(n).
Loop running constant multiple of n: O(n).
for(int i = 1; i <= c*n; i = i + 1)
{
Some O(1) expressions
}Here loop is running cn times and performing O(1) operation at each iteration. 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
}Based on some conditions, we are either incrementing l or decrementing r by 1 and performing O(1) operation at each iteration. Here loop will run n times because l and r are starting from opposite ends and stop when l > r. So time complexity = n * O(1) = O(n).
Loop incrementing or decrementing exponentially by factor of 2: O(logn)
Example 1: Loop incrementing by factor of 2.
for(int i = 1; i < n; i = i*2)
{
Some O(1) expressions
}
// while loop version
int i = 1;
while(i < n)
{
Some O(1) expressions
i = i * 2;
}Example 2: Loop decrementing by factor of 2.
for(int i = n; i > 0; i = i/2)
{
some O(1) expressions
}
// while loop version
int i = n;
while(i > 0)
{
Some O(1) expressions
i = i / 2;
}In the above examples, the loop runs from 1 to n, and the loop variable increases or decreases by a factor of 2 at each iteration. To calculate the time complexity, we need to count the total number of iterations performed by the loop.
Let’s assume the loop will terminate after the k steps. So by the end of the loop, 2^k must be equal to the n. => 2^k = n => k = logn. So the loop will run logn number of times and perform O(1) operation at each step. Time complexity = k * O(1) = 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
}In this case, the loop runs from 1 to n, and the loop variable increases by a factor of i^c. How do we calculate the total number of loop iterations? Let's think.
- The first iteration starts with i = 2.
- In the second iteration, the value of i is 2^c.
- In the third iteration, the value of i is (2^c)^c = 2^(c²).
- This pattern continues until the end. At the ith iteration, the value of i is 2^(c^i).
- The 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)So the loop will run log(log(n)) number of times, where each iteration will take O(1) time. So overall time complexity = 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 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).
Analysis of nested loop patterns
Two nested loop: 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 example, the inner loop is running n times for every iteration of the outer loop. So the total number of loop iterations = Total iteration of the outer loop * Total iteration of the inner loop = n * n = n². At each step of the iteration, nested loop is doing O(1) operation. So overall time complexity = 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 example, at every iteration of the outer loop, inner loop is running (n - i) times. So number of loop iterations = (n - 1) + (n - 2) + (n - 3)…..+ 2 + 1 = Sum of values from (i = 0 to n - 1) = n(n - 1)/2 = n²/2 - n/2 = O(n²). At each iteration, nested loop is performing O(1) operation. So overall time complexity = O(n²) * O(1) = O(n²).
Let's take an interesting example. Suppose, we have an input matrix X of size m x n containing only 0's and 1's, which are sorted in a row-wise fashion. What will be the time complexity of this loop?
int j = n - 1;
for(int i = 0; i < m; i = i + 1)
{
while(j >= 0 && X[i][j] == 1)
{
j = j - 1;
// Some O(1) operation
}
}If we observe closely, the outer loop iterates over rows, and the inner loop iterates over columns independently. Thus, the nested loop will traverse each row and column once in the worst case. So, the total loop iterations = Total number of rows + Total number of columns = m + n. At each loop iteration, we are performing an O(1) operation. So time complexity = Total loop iteration*O(1) = (m + n) * O(1) = O(m + 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
In such a case, we need to do the sum of the time complexities of each loop, but time complexity will be 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
}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 loops, the outer loop runs n - 1 time and two inner loops run n - i and j - i + 1 time. So what would be the total count of nested loop iterations? Let’s think.
n - 1 n j
T(n) = ∑ ∑ ∑ O(1)
i = 1 j = i + 1 k = iNow we solve this summation by expanding the summation one by one.
Higher-order term in T(n) is n^3, so T(n) = O(n^3). We are ignoring lower-order terms and coefficients. Note: There is one error in the third line of the above image. Instead of + i(n - i), it would be - i (n - i).
We recommend to explore these problems to explore more about the time complexity analysis of loop
- Rotate a matrix by 90 degrees
- Print matrix in spiral order
- Detect loop in a linked List
- Sort a stack using another stack
- Implement queue using stacks
- Implement stack using queues
- Level order traversal of a binary tree
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!