evaluating time complexity of a code 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&gt;2
            j=1
            while j&lt;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?
Your recurrence is
$$
T(n) = \begin{cases}
T(n-1) + n &amp; \text{if $n&gt;1$ is odd}, \\
2T(n-1) + \log n &amp; \text{if $n$ is even}, \\
1 &amp; \text{if $n=1$}.
\end{cases}
$$
We can convert it to a more amenable pair of recurrences. If $n &gt; 1$ is odd then
$$
T(n) = T(n-1) + n = 2T(n-2) + n + \log(n-1).
$$
If $n &gt; 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) &amp; \text{if $m &gt; 0$}, \\
1 &amp; \text{if $m = 0$}.
\end{cases} \\
T(2m) =
\begin{cases}
2T(2(m-1)) + 2(2m-1) + \log(2m) &amp; \text{if $m &gt; 1$}, \\
2 + \log 2 &amp; \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})$.