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?

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

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.