educative.io

Nested For-loop With Index Modification - clarification on log2(n-1)

Courses
,
#1

I am not understanding why we are saying that i in the outer loop iterates until n-1 and not n. In a nested for-loop with dependent variable example the outer loop is said to run n time and inner loop n-1 times. With the index modification we are saying it runs log2(n-1) times, I thought it would be log2(n)

Course: https://www.educative.io/courses/big-o-notation
Lesson: Educative: Interactive Courses for Software Developers

#2

Hi @Georges_Chami !!
In the case of the nested for-loop with dependent variables, the reason why we are saying that the outer loop iterates until (n-1) and not (n) is because of how the nested loops are structured. Let’s revisit the specific example and see the iterations of the nested for-loop with dependent variables:

for (int i=0; i<n; i++){
    for (int j=0; j<i; j++){
        //Statement(s) that take(s) constant time
    }
}

When the outer loop runs, the inner loop depends on the value of the outer loop variable (i). For the first iteration of the outer loop, (i) is 0, so the inner loop doesn’t run at all. In the second iteration of the outer loop, (i) is 1, so the inner loop runs once. In the third iteration of the outer loop, (i) is 2, so the inner loop runs twice. This pattern continues until the last iteration of the outer loop when (i) is (n-1). Hence, the inner loop runs (0+1+2+\cdots+(n-2) = \frac{n(n-1)}{2}) times.

The reason we have (n-1) instead of (n) in the formula is that the loop is programmed to stop when the condition (i < n) is no longer true. Therefore, the value of (i) will be at most (n-1) when the loop terminates.

In nested-for loop with index modification:

for (int i=0; i<n; i++){
    i*=2;
    for (int j=0; j<i; j++){
        // Statement(s) that take(s) constant time
    }
}

This code snippet includes two nested loops. Let’s break down the execution step by step:

  1. The outer loop initializes the variable (i) to 0 and runs until (i) is less than (n). However, inside the loop, the value of (i) is modified by doubling it in each iteration (i *= 2). This means the sequence of (i) values is as follows: 0, 0 (doubled from the initial value), 0 (doubled from the second value), 0 (doubled from the third value), and so on until (i) exceeds (n).
  2. The inner loop depends on the value of (i) from the outer loop. It runs until (j) is less than (i) and executes the constant-time statement(s) inside the loop.

Let’s break down the iterations:

  • Initially, (i) is 0, so the inner loop doesn’t run.
  • After the first iteration of the outer loop, (i) is 0. However, due to the modification in the loop, it remains 0.
  • After the second iteration of the outer loop, (i) is 0 (doubled from the previous value, which was also 0).
  • After the third iteration of the outer loop, (i) is 0 (doubled from the previous value, which was also 0).
  • The pattern continues until (i) exceeds (n).

Although the exact number of iterations can be difficult to discern due to the doubling nature of (i) and the modification within the loop, we can simplify the analysis by considering that (i) is doubled each time until it exceeds (n). This doubling pattern leads us to an approximate logarithmic behavior.

So, in the case of the nested for-loop with index modification, the reason we say it runs approximately (\log_2(n-1)) times instead of (\log_2(n)) is that the loop doesn’t reach exactly (n) but stops at (n-1) because of the condition (i < n) in the loop statement.
I hope it helps. Happy Learning :blush:

1 Like