Runtime analysis of while-loop analysis
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 &gt; 4)
  if (s is even)
      s = s / 2
  else 
      s = s - 1 


Anyway, let's start with your recursion formula.

Consider $n&gt;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&gt;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 &lt; 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.