# Runtime analysis of while-loop analysis

s = n
while (s > 4)
s = s / 2
else
s = s - 1


Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs.

$S(n)=1 + S(n/2)$ if $n$ is even

$S(n)=1 + S(n-1)$ if $n$ is odd

$S(n)=0$ if $n \leq 4$

By converting n to a binary number, and I think

if $n < 2^k$, then $S(n) \leq k - 1$

I have come to this relationship, yet can't figure out how to approach to $\Theta$ bound.

Any help or guidance is appreciated.

• I suggest you look up the Master's theorem and methods to solve Recurrence relations by substitution. When n is even, using the master theorem, you can easily determine the complexity is log(n) and using the method of substitution when n is odd, the complexity is n. – Gary Andrews30 May 16 '18 at 1:05
• But this is not recursive @GaryAndrews30 – user87320 May 16 '18 at 1:10
• All iterative algorithms can be expressed recursively. Since you can build a Turing complete language using strictly iterative structures and a Turning complete language using only recursive structures, then the two are therefore equivalent. – Gary Andrews30 May 16 '18 at 1:14

It is a strange grammar that while is combined with else in your pseudocode. There is such grammar in Python but it is obviously not the case. I guess you mean

s = n
while (s > 4)
if (s is even)
s = s / 2
else
s = s - 1


Consider $n>4$. Note if $n$ is even, $S(n)=1+S(n/2)=1+S(\lfloor n/2\rfloor)$, and if $n$ is odd, $S(n)=1+S(n-1)=2+S((n-1)/2)=2+S(\lfloor n/2\rfloor)$. So anyway, for $n>4$ we have

$$1+S(\lfloor n/2\rfloor)\le S(n)\le 2+S(\lfloor n/2\rfloor).\quad (1)$$

Suppose $2^{k-1}\le n < 2^k$, you can prove

$$k-2\le S(n)\le 2(k-2).$$

using mathematical induction (the formal proof is left to you as an exercise). So $S(n)=\Theta(k)=\Theta(\log_2 n)$.

From (1) we can write $S(n)=S(\lfloor n/2\rfloor)+f(n)$ where $1\le f(n)\le 2$, i.e. $f(n)=O(1)$. Then Master Theorem applies.

• Isn’t it k on the left side ？thank you so much from the answer ! Got the idea from this :) – user87320 May 16 '18 at 3:35
• @VioletOlive It is $k-2$. You can try $n=6$ with $k=3$. – xskxzr May 16 '18 at 3:46