Time Complexity Analysis of Nested Loops: Big O Notation

In analyzing the efficiency of algorithms, particularly in terms of time complexity, Big O Notation is a fundamental concept. This article delves into the time complexity of a given piece of nested loop code, using Big O Notation to express the upper bound on the time required by the algorithm as a function of input size.

Code Structure

The code structure under analysis is as follows:

for (int I  1; I  n; I  ) {
    for (int j  0; j  I; j  ) {
        if (j % I  0) {
            for (int k  0; k  j; k  ) {
                sum;
            }
        }
    }
}

Loop Analysis

Outer Loop

The outer loop runs for I from 1 to n - 1. This means the outer loop runs n - 1 times or O(n).

Middle Loop

The middle loop runs for j from 0 to I - 1. Therefore, it iterates I times for a given I.

If Statement

The condition if (j % I 0) checks if j is a multiple of I. The multiples of I in the range [0, I - 1] are 0, I, 2I, ..., (I - 1)I. The number of such multiples is I.

Innermost Loop

The innermost loop runs for k from 0 to j - 1, meaning it runs j times.

Total Count of Operations

To calculate the total number of operations:

For each I, the middle loop runs I times. However, the innermost loop only operates for the values of j that are multiples of I. The relevant values of j are 0, I, 2I, ..., (I - 1)I

The total contribution from the innermost loop for a specific I can be calculated as follows:

The innermost loop will run for j 0 0 times, j I I times, j 2I 2I times, ..., up to j (I - 1)I, which is (I - 1)I times. The sum of these values is:

0 * I I * I 2I * I ... (I - 1)I * I I2 * (0 1 2 ... I - 1) I2 * (I - 1)/2 (I2(I - 1))/2

The final complexity will be summation over all I from 1 to n - 1:

total operations Σ (I2(I - 1))/2 for I 1 to n - 1

This can be approximated as:

O(Σ I4 for I 1 to n) O(n5)

Thus, the overall time complexity of the given code is:

Big O O(n5)

Code Example

Here is the code in C:

#include stdio.h
int main() {
    int n, sum  0;
    scanf("%d", n);
    for (int I  1; I  n; I  ) {
        for (int j  0; j  I; j  ) {
            if (j % I  0) {
                for (int k  0; k  j; k  ) {
                    sum  ;
                }
            }
        }
    }
    printf("%d
", sum);
    return 0;
}

If implemented correctly, this piece of code will have an overall time complexity of O(n5).

Conclusion

Understanding and expressing the time complexity of algorithms using Big O Notation is crucial for optimizing code and improving its efficiency. In the context of this nested loop code, the overall complexity is O(n5) as analyzed above.