educative.io

Initialization of j

Courses
,
#1

Hi,

In the following code, shouldn’t the initialization of j be inside the outer for loop before entering the while loop for the inner while loop to have O(n)lgn complexity? Since it is initialized outside the outer for loop, when var=1, the entire while loop will run to completion (O(lgn)) and next time onwards (var=4, 7 etc.) the while (j<n) condition will exit immediately.

int n = 10;   
int sum = 0;  
int j = 1;  
double pie = 3.14;   

for (int var = 1; var < n; var += 3) {  // O(n/3)
  System.out.println("Pie: " + pie); //O(1)    // O(n/3)
  while (j < n) {    // O((n/3)*(log3 n))
    sum += 1;      // O((n/3)*(log3 n))
    j *= 3;       // O((n/3)*(log3 n))
  }
}

Thanks,
Lakshmi

#2

Hi Lakshmi,

One more issue I would like to add is :
The inner loop statements sum+=1 and j *=3 should be executed log3 (n-1) times rather than log3 n times
when we have n = 9
inner loop statements will only run twice