simple time complexity O(nlogn)

Question

I am reviewing some Big O notation for an interview and I come across this problem.

for i = 1 to n do:
    j = i
    while j < n do:
    j = 2 * j

simple right? the outer loop provides n steps. and each of those steps we do a single step O(1) of assignment j=i then log(n-j) or log(n-i) since j = i step for the while loop. I thought the time complexity would be O(nlogn) but the answer is O(n).

here is the answer:

The running time is approximately the following sum: Σ 1 + log(n/i) for i from 1 to n which is Θ(n).

Now it has been a while so I am a bit rusty. where does log(n/i) comes from? I know log(n) - log(i) = log(n/i) however I thought we log(n-i) not log(n) - log(i). and how is the time complexity not O(nlogn)? I am sure I am missing something simple but I been staring at this for hours now and I am starting to lose my mind.

source: here is the source to this problem Berkeley CS 170, Fall 2009, HW 1

edit: after thinking about it a little more it makes sense that the time complexity of the inner loop is log(n/i). cause each inner loop runs n-i times but i double each loop. if the inner loop were always starting at 0 we have log(n) but take into account the number of the loop we don't have to loop over which is log(i). log(n) - log(i) which is log(n/i).

user_2835764 · Answer

I think the log(n/i) comes from the inner loop

notice how j = i

which means when i=2 (lets say n=10)

the inner loop

while j < n do:
    j = 2 * j

will run only from j=2 to 10 where j multilplies itself by 2 (hence the log) & quickly overruns the value of n=10

so the inner loop runs log base 2 n/i times

i ran a simple i=10 through the code & it looks like linear time because most of the time inner loop runs only once.

example : when the value of i becomes such that if you multiply it by 2, you get greater than or equal to n, you don't run the inner loop more than once.

so if n=10 you get one execution in the inner loop starting from i=n/2 (if i=10/2=5) then j starts with j=5, gets in the loop once multiplies itself with 2 & the inner loop condition while j < n do: fails.

EDIT : it would be O(n.log(n)) if the value of j started with j=0 everytime & the inner loop ran from i to n

simple time complexity O(nlogn)

1 Answers