educative.io

Why Complexity Of while loop is nLog(n)

Courses
,
#1

The solution says that the instruction

while (var < n)

is executed <= n*log(n) times. I am not able to follow why that be the case. According to be, it should be no more than log(n) times.

#2

Hi Rajiv,

Thanks for reaching out!

As you may see in the code:

while(var < n) {
			System.out.println("Pie: " + pie);
			//O(?)
			for (int j = 0; j <= var; j++) {
				sum++;
			}
      var*=2;
		} //end of while loop

The outer loop while (var < n) runs log(n) times because var increments by doubling (var * 2) each time.
Meanwhile, the inner for loop runs no more than n times.

Therefore, the combined complexity of the snippet becomes nlog(n).

We have updated the existing solution for your better understanding.

Hope you got your ambiguities removed.
If you have any further questions/suggestions/feedback, we’ll be happy to hear!

Thanks and Regards,
Lubaina Khan | Developer Advocate

#3

Please update the page