educative.io

Educative

Why Complexity Of while loop is nLog(n)

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.

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

Please update the page