?? Understanding Time Complexity in Nested Loops ??

Let's analyze the time complexity of the following PHP code:

$n = 2;
for ($i = 1; $i <= $n; $i++) {
     for ($j = 1; $j <= $n; $j *= 2) {
         echo "Hello World";
      }
}        

Time Complexity Analysis:

Outer Loop (for($i = 1; $i <= $n; $i++)):

This loop runs from i = 1 to i = n, hence it iterates n times.

Inner Loop (for($j = 1; $j <= $n; $j *= 2)):

This loop starts with j = 1 and in each iteration, j is multiplied by 2.

The number of iterations of this loop is logarithmic in terms of n because j doubles each time. Specifically, it runs O(log n) times.

Combined Time Complexity:

To find the combined time complexity, let's multiply the complexities of the two loops:

Outer loop: O(n)

Inner loop: O(log n)

Thus, the overall time complexity is:

??(???log??)

O(n?logn)

Example Trace

For ??=2

n=2:

Outer loop runs 2 times (i = 1, 2).

Inner loop runs log2(n) times. For n = 2, log2(2) is 1, so it runs once for each iteration of the outer loop.

So the time complexity is O(n \log n).