Complexity of an algorithm with two recursive calls

Question

I have a strange algorithm than is being called recursively 2 times. It's

int alg(int n)
   loop body = Θ(3n+1)
   alg(n-1);
   alg(n-2)

Somehow i need to find this algorithm's complexity. I've tried to find it with using characteristic polynomial of the above equation but the result system is too hard to solve so i was wondering if there was any other straight way..

Answer 1

johnchen902 is correct:

alg(n)=Θ(φ^n) where φ = Golden ratio = (1 + sqrt(5)) / 2

but his argument is a bit too hand-waving, so let's make it strict. His original argument was incomplete, therefore I added mine, but now he has completed the argument.

---

loop body = Θ(3n+1)

Let us denote the cost of the loop body for the argument n with g(n). Then g(n) ∈ Θ(n) since Θ(n) = Θ(3n+1).

Further, let T(n) be the total cost of alg(n) for n >= 0. Then, for n >= 2 we have the recurrence

T(n) = T(n-1) + T(n-2) + g(n)

For n >= 3, we can insert the recurrence applied to T(n-1) into that,

T(n) = 2*T(n-2) + T(n-3) + g(n) + g(n-1)

and for n > 3, we can continue, applying the recurrence to T(n-2). For sufficiently large n, we therefore have

T(n) = 3*T(n-3) + 2*T(n-4) + g(n) + g(n-1) + 2*g(n-2)
     = 5*T(n-4) + 3*T(n-5) + g(n) + g(n-1) + 2*g(n-2) + 3*g(n-3)
     ...
                                       k-1
     = F(k)*T(n+1-k) + F(k-1)*T(n-k) +  ∑ F(j)*g(n+1-j)
                                       j=1

                                 n-1
     = F(n)*T(1) + F(n-1)*T(0) +  ∑ F(j)*g(n+1-j)
                                 j=1

with the Fibonacci numbers F(n) [F(0) = 0, F(1) = F(2) = 1].

T(0) and T(1) are some constants, so the first part is obviously Θ(F(n)). It remains to investigate the sum.

Since g(n) ∈ Θ(n), we only need to investigate

       n-1
A(n) =  ∑ F(j)*(n+1-j)
       j=1

Now,

                 n-1
A(n+1) - A(n) =   ∑ F(j) + (((n+1)+1) - ((n+1)-1))*F((n+1)-1)
                 j=1

                n-1
              =  ∑ F(j)  + 2*F(n)
                j=1

              = F(n+1) - 1 + 2*F(n)
              = F(n+2) + F(n) - 1

Summing that, starting with A(2) = 2 = F(5) + F(3) - 5, we obtain

A(n) = F(n+3) + F(n+1) - (n+3)

and therefore, with

c*n <= g(n) <= d*n

the estimate

F(n)*T(1) + F(n-1)*T(0) + c*A(n) <= T(n) <= F(n)*T(1) + F(n-1)*T(0) + d*A(n)

for n >= 2. Since F(n+1) <= A(n) < F(n+4), all terms depending on n in the left and right parts of the inequality are Θ(φ^n), q.e.d.

Answer 2

Complexity: alg(n) = Θ(φ^n) where φ = Golden ratio = (1 + sqrt(5)) / 2

I can't formally prove it at first, but with a night's work, I find my missing part - The substitution method with subtracting a lower-order term. Sorry for my bad expression of provement (∵ poor English).

---

Let loop body = Θ(3n+1) ≦ tn

Assume (guess) that cφ^n ≦ alg(n) ≦ dφ^n - 2tn for an n (n ≧ 4)

Consider alg(n+1):

 Θ(n) + alg(n) + alg(n-1) ≦ alg(n+1) ≦ Θ(n) + alg(n)     + alg(n-1)
    c * φ^n + c * φ^(n-1) ≦ alg(n+1) ≦ tn   + dφ^n - 2tn + dφ^(n-1) - 2t(n-1)
              c * φ^(n+1) ≦ alg(n+1) ≦ tn   + d * φ^(n+1) - 4tn + 2
              c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 3tn + 2
              c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 2t(n+1)  (∵ n ≧ 4)

So it is correct for n + 1. By mathematical induction, we can know that it's correct for all n.

So cφ^n ≦ alg(n) ≦ dφ^n - 2tn and then alg(n) = Θ(φ^n).