evaluating time complexity of a code
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})$.