# 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>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?

• You can split in $T_o(n)$ and $T_e(n)$ and establish a system of recurrence equations. – Yves Daoust Aug 26 '19 at 19:26
• To calculate 2 * foo (n-1), you only evaluate f (n-1) once. And multiply the result by 2. Remember you are looking for the time complexity, not for the function value. – gnasher729 Aug 26 '19 at 19:33
• In the even case there's a log squared (check what happens if n = 3^100), but it doesn't matter because the odd case is so much bigger. – gnasher729 Aug 26 '19 at 19:36
• @YvesDaoust if I evaluate them separately I get $T_o(n) = \theta(n^2)$ and $T_e(n) = \theta(2^n)$ what is the actual answer? – Ed_ Aug 26 '19 at 19:44
• Possible duplicate of Is there a system behind the magic of algorithm analysis? – dkaeae Aug 27 '19 at 7:15

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})$$.