educative.io

Calculation of time complexity for inner loop is wrong

Courses
,
#1

class NestedLoop {

public static void main(String[] args) {

int n = 10;   // O(1)

int sum = 0;  // O(1)

int j = 1;    // O(1)

double pie = 3.14; // O(1)

for (int var = 0; var < n; var++) {  // 0(n)

 

  System.out.println("Pie: " + pie); // 0(n)

  while(j < var) { // 0(n)

    sum += 1;  // 0(n)

    j *= 2;  // 0(n)

  }

} //end of for loop

System.out.println("Sum: " + sum); // O(1)

} //end of main

} //end of class

Here in while loop its give that it will run o(n) time which is true when var is 0,1 but when var is 2 the while condition becose true and j will increase to 2 then the condition will fail so here the loop executed two times in the smae way when var is 2 , 5, 9, 17 … loop will execute 2 times

Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

#2

Hi @vineeth_sagar
Time complexity calculation for the inner loop is not wrong, you might be misunderstood. Let me clear you up again.

The outer loop in the main function has n iterations as it iterates on i from 0 to n-1. If the condition j < i is true, the inner loop is entered. However, immediately, j is doubled. Note that j is not reset to 1 in the code since the j is immediately doubled, therefore inner while loop will run O(log2​(n)) times for all the iterations of the outer loop. The inner while loop will run at most once for each iteration of the outer loop.

Hope it will help, Thanks :blush: