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