1
$\begingroup$
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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gary Andrews30 May 16 '18 at 1:05
  • $\begingroup$ But this is not recursive @GaryAndrews30 $\endgroup$ – user87320 May 16 '18 at 1:10
  • $\begingroup$ 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. $\endgroup$ – Gary Andrews30 May 16 '18 at 1:14
1
$\begingroup$

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 

Anyway, let's start with your recursion formula.

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy