evaluating time complexity of a code

Question

I'm trying to evaluate the time complexity of the following :

foo (n)
    if n ≤ 1
        return 1
    if n is odd
        for i=1 to n
            print i
        return foo(n-1) + 1
    if n is even
        i=n
        while i>2
            j=1
            while j<i
                j=j*2
            i=i/3
        return 2 * foo(n-1)

my attempt was to produce a recurrence relation broken into cases:

if $n \leq 1$ then :

$T(n)=\theta(1)$

if $n $ is odd then the for loop is executed $n$ times and we return a problem of size $n-1$ so :

$T(n)= T(n-1) + \theta(n)$

if $n$ is even then the inner while loop is executed $\theta(log_6(n))$ times and the outer while loop is executed $O(log_3(n)) $ times so totally that would be $O(log_3(n))= O(log(n))$ , and we return a problem of size $n-1$ twice so:

$T(n) = 2T(n-1) + O(log(n))$

ultimately :

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

$T(n) = 2T(n-1)+log(n) $ if $n$ is even

$T(n) = 1 $ if $n = 1$

since whenever $n$ is odd , $n-1 $ is even , $n-2 $ is odd and so on.. that had me confused. Any ideas of how to solve this?

Answer 1

Your recurrence is $$ T(n) = \begin{cases} T(n-1) + n & \text{if $n>1$ is odd}, \\ 2T(n-1) + \log n & \text{if $n$ is even}, \\ 1 & \text{if $n=1$}. \end{cases} $$ We can convert it to a more amenable pair of recurrences. If $n > 1$ is odd then $$ T(n) = T(n-1) + n = 2T(n-2) + n + \log(n-1). $$ If $n > 2$ is even then $$ T(n) = 2T(n-1) + \log n = 2T(n-2) + 2(n-1) + \log n. $$ Finally, $$ T(2) = 2T(1) + \log 2 = 2 + \log 2. $$

We obtain the two recurrences $$ T(2m+1) = \begin{cases} 2T(2(m-1)+1) + (2m+1) + \log (2m) & \text{if $m > 0$}, \\ 1 & \text{if $m = 0$}. \end{cases} \\ T(2m) = \begin{cases} 2T(2(m-1)) + 2(2m-1) + \log(2m) & \text{if $m > 1$}, \\ 2 + \log 2 & \text{if $m = 1$}. \end{cases} $$ Both recurrences are of the form $S(m) = 2S(m-1) + \Theta(m)$. The simplest way of solving this is considering $R(m) = S(m)/2^m$, which satisfies the recurrence $R(m) = R(m-1) + \Theta(m/2^m)$. Since $\sum_{m=0}^\infty m/2^m$ converges, we see that $R(m) = \Theta(1)$ and so $S(m) = \Theta(2^m)$. This implies that $T(2m+b) = \Theta(2^m)$ (for $b=0,1$), and so $T(n) = \Theta(2^{n/2})$.