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$
9
  • 1
    $\begingroup$ You can split in $T_o(n)$ and $T_e(n)$ and establish a system of recurrence equations. $\endgroup$
    – user16034
    Aug 26, 2019 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, 2019 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, 2019 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$
    – giorgioh
    Aug 26, 2019 at 19:44
  • 2
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$
    – dkaeae
    Aug 27, 2019 at 7:15

1 Answer 1

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 and acknowledge you have read our privacy policy.

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