# Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$

I know for a fact that algorithm A runs in $$\Theta(n)$$, but how does one derive that?

Algorithm A

i = 1
while i ≤ n
s = 0
while s ≤ i
s = s + 1
i = 2 ∗ i


The inner loop is clearly $$O(i)$$ (linear time).

The outer loop is clearly $$O(\log n)$$ (logarithmic time).

A visualitation of the loop in terms of an input $$n$$ would look as follows:

, the black lines represents the amount of work or iterations required in terms of $$n$$.

$$\sum_{i=1}^k 2^i=\Theta(2^k)$$ and you have $$k\approx\log n$$, so the sum is $$\Theta(2^{\log n})=\Theta(n)$$.
• Which part do you need help with? The sum is the total amount of time spent in the inner loop if the outer loop executes $k$ times. – David Richerby Oct 3 '19 at 8:52
• Okay, so the inner loop runs $\sum_{i=1}^{k}2^i=2+4+8+...+k$ times ... I get that. First off, that summation is equal to $2^{k+1}-1$. As far as I am concerned, $2^{k+1}-1 \neq \Theta(2^k)$. What do you have to say about that? – Sebastian Nielsen Oct 3 '19 at 20:24
• @SebastianNielsen I say that, for all $k\geq 0$, $1\times 2^k\leq 2^{k+1}-1 < 2\times 2^k$ so $2^{k+1}=\Theta(2^k)$. – David Richerby Oct 3 '19 at 23:35
• "$k$ is the total amount of time spent in the inner loop if the outer loop executes $k$ times", which is $k\approx \log n$ ... okay, so why isn't this $\log n$ the answer (the time complexity)? Why did you (this is what I assume you did) substitute $k$ in the term $2^k$ with $\log n$ to get $Theta(2^{\log n})$? You just found out how many times the inner loop executes in terms of $n$ ... why isn't this the answer ($k\approx \log n$)? – Sebastian Nielsen Oct 4 '19 at 6:30