A Beginner’s Guide to Analyzing For Loop Complexities

INTRODUCTION

Time and space complexity are essential for evaluating the efficiency of algorithms. Loops, being fundamental to programming, significantly affect these complexities depending on their structure.

Simple loops have a time complexity of $O (n)$ and a space complexity of $O (1)$ .
Nested loops increase time complexity with each level, e.g., $O(n^2)$ for two loops and $O(n^3)$ for three, while space remains $O (1)$ .
Logarithmic loops, where the iterator doubles or halves, have a time complexity of $O(log⁡n)O(\log n)$ and a space complexity of $O (1)$ .

Efficient loop analysis is key to writing optimized and scalable code.

The time complexity and space complexity of different for loops can vary depending on factors like the number of iterations and what operations are performed inside the loop. Let’s break down common cases:

Simple Loop

for ( i = 0; i < numbering; i++) {

}

Time Complexity: O(n)
Space Complexity: O(1)

Nested Loops

for (i= 0; i < numbering; i++) {

for ( j = 0; j < numbering; j++) {

}

Time Complexity:O(p2)
Space Complexity: O(1)

Loop with a Non-constant Step

for (i = 20; i < p; i -= 2) {

}

Time Complexity:o(n)
Space Complexity: O(1)

Loop with a Logarithmic Growth (Doubling or Halving)

for (int i = 1; i < number; i *= 2) {

}

Time Complexity: (o(logn))
The space complexity : O(1)

Loop with a Non-constant Step (Sublinear or Complex)

for (int i = 1; i < number; i = i * 3) {

// O(1) operation

}

Time Complexity: The loop runs while i is less than n, and i is multiplied by 3 each time. The number of iterations is O(log⁡3n) which is still O(log⁡n)as the base of the logarithm does not affect the overall complexity.
Space Complexity: O(1)

Loop with Multiple Nested Loops (for example, 3 levels)

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

for(int k=0;k<n;k++)

}

Time Complexity: This is a triple nested loop, each running n times, so the time complexity is O(p3)
Space Complexity: The space complexity is O(1), assuming no extra data structures are created.

Summary:

Simple loop: O(n) time, O(1) space.
Nested loops: The time complexity increases based on the number of nested loops, e.g., O(n2) for 2 nested loops, O(n3) for 3, etc.
Logarithmic growth: O(logn) time, O(1)

Must Read: STM32 ADC: Analog Sensor Reading