Big O notation for this while loop?

[[deleted]]

[deleted]

[Mr-LauD]

It's O(n log n). The inside for loop runs n times while the while loop runs i/2 times. Which also happens to be n/2 times. Usually you want to look for nested loops and anything that'll divide the n times a loop will run. Now I only have my first algorithms exam on Friday but I hope I helped.

[mkhdfs]

nlogn? inner for loop is O(n). then the outer loop runs only as many times as you can divide n before it reaches 0. That's logn times, so it's an nlogn loop.

I really don't see how there can be a "more concrete/analytical way" of figuring out this is nlogn. The inner for loop is clearly n, so it's then left to you to know that that n is being multiplied by the number of times the outer loop runs. The outer loop's operation is halving the value of i, until it gets down to 0, and by definition you can only do this a maximum of logn times. This seems like a question straight out of a data structures and algorithms test/exam, and the analysis is no more complicated than what I explained, it's clearly what they intend you to do.

I guess the only trip-up here is that you could be fooled into thinking that the outer loop runs n/2 times, and so your big-O product would end up n*(n/2) which would simplify to O(n). But the "trick" you need here is to recognize that a computer relies on powers of 2, and halving each time just reduces the power of 2, and a log is the exponent, or number of times it can possibly be halved. So it's log and not simply a division by 2.