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?