2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You can split in $T_o(n)$ and $T_e(n)$ and establish a system of recurrence equations. $\endgroup$ – Yves Daoust Aug 26 at 19:26
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Aug 26 at 19:33
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Aug 26 at 19:36
  • $\begingroup$ @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? $\endgroup$ – sadElephent Aug 26 at 19:44
  • 2
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – dkaeae Aug 27 at 7:15
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.