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

Question

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$.

Answer 1

$\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)$.