Time complexity for the following algorithm?

Question

I am studying Big-O notation right now and stumbled upon this little algorithm in another thread:

i = n while (i >= 1) { for j = 1 to i // NOTE: i instead of n here! { x = x + 1 } i = i/2 } 

According to the author of the post, the complexity is Θ (n), but I cannot figure out how to do this. I think the complexity of the while loop is Θ (log (n)). The complexity of the for loop from what I thought would also be Θ (log (n)), because the number of iterations would be halved each time.

So, won't the complexity of all this be Θ (log (n) * log (n)), or am I doing something wrong?

Edit: the segment is in the best answer to this question: https://stackoverflow.com/a/4648772

Answer 1

Imagine for simplicity that n = 2^k . How many times does x increase? The geometric series easily follows from this.

2 ^ k + 2 ^ (k - 1) + 2 ^ (k - 2) + ... + 1 = 2 ^ (k + 1) - 1 = 2 * n - 1

So this part is Θ(n) . In addition, i gets half k = log n times and does not have an asymptotic effect for Θ(n) .

Answer 2

The value of i for each iteration of the while , as well as the number of iterations of the for loop equal to n, n / 2, n / 4, ... and the total complexity is the sum. This puts it in about 2n, which gives you your Theta (n).