Complexity of an algorithm with two recursive calls

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

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.

Assumptions:

1: n >= 0

2: Θ(3n+1) = 3n + 1

Complexity:

O(2 ^ n * (3n - 2));

Reasoning:

int alg(int n)
   loop body = Θ(3n+1)// for every n you have O(3n+1)
   alg(n-1);
   alg(n-2)

Assuming the alg does not execute for n < 1, you have the following repetitions:

Step n:

3 * n + 1
alg(n - 1) => 3 * (n - 1) + 1
alg(n - 2) => 3 * (n - 2) + 1

Now you basically have a division. You have to imagine a number tree with N as parent and n-1 and n-2 as children.

                                       n
                 n-1                                  n-2
          n - 2        n - 3                     n - 3       n - 4
     n - 3   n - 4   n - 4 n - 5              n - 4 n - 5  n - 5  n - 6
    n-4 n-5 | n-5 n-6 |n-5 n-6 |n-6 n-7    n-5 n-6 n-6 n-7  n-6 n-6| n-6 n-8

It's obvious that there is a repetition pattern here. For every pair (n - k, n - k - 1) in A = {k, with k from 0 to n) except the first two and the last two, (n - 1, n - 2) and (n-2, n-3) there is a 3k + 1 * (2 ^ (k - 1)) complexity.

I am looking at the number of repetitions of the pair (n - k, n - k - 1). So now for each k from 0 to n I have:

(3k + 1) * (2 ^ (k - 1)) iterations.

If you sum this up from 1 to n you should get the desired result. I will expand the expression:

(3k + 1) * (2 ^ (k - 1)) = 3k * 2 ^ (k - 1) + 2 ^ (k - 1)

Update

1 + 2 + 2^2 + 2^3 + ... + 2^n = 2 ^ (n + 1) - 1

In your case, this winds up being:

2^n - 1

Based on the summation formula and k = 0, n . Now the first one:

3k * 2 ^ (k - 1)

This is equal to 3 sum from k = 0, n of k * 2 ^ (k - 1). That sum can be determined by switching to polinomial functions, integrating, contracting using the 1 + a ^ 2 + a ^ 3 + ... + a ^ n formula, and then differentiated again to obtain the result, which is (n - 1) * 2 ^ n + 1.

So you have:

2 ^ n - 1 + 3 * (n - 1) * 2 ^ n + 1

Which contracted is:

2 ^ n * (3n - 2);

The body of the function takes Θ(n) time. The function is called twice recursively.

For the given function the complexity is,

     T(n) = T(n-1) + T(n-2) + cn        -----  1
     T(n-1) = T(n-2) + T(n-3) + c(n-1)  -----  2

1-2 ->   T(n) = 2T(n-1) - T(n-3) + c        -----  3

3 -->    T(n-1) = 2T(n-2) + T(n-4) + c      -----  4

3-4 ->   T(n) = 3T(n-1) - 2T(n-2) - T(n-3) - T(n-4) ----- 5

Let g(n) = 3g(n-1)

There for, we can approximate T(n) = O(g(n))

g(n) is Θ(3ⁿ)

There for T(n) = O(3ⁿ)