This question already has an answer here:
I am trying to determine the worst case runtime of this program:
while n > 1 for i = 1,..,n m = log(n) n = n/2
Obviously the outer loop runs
log(n) times, because n is halfed after each step.
But the inner for loop is dependent on the decreasing n and I am not quite sure how to deal with that.
A simple bound for it would be
n, so the whole thing runs in at most
log(n)*n, but I am sure the inner loop is faster than that.
If I look at each step of the outer loop, I see that the inner loop runs
n,n/2,n/4,..,2 times. So I would say all together the inner loop runs at most
2n times which is in
Can I just deduct from that fact that the overall runtime is
O(log(n)+n) = O(n)?
I am unsure because I am not multiplying anything, which I feel like I should when dealing with multiple loops.