I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?
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: