The complexity of an algorithm with two recursive calls

Question

I have a weird algorithm called recursively 2 times. it

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

Somehow I need to find this complexity of the algorithm. I tried to find it using the characteristic polynomial of the above equation, but the result system is too complicated to solve, so I was wondering if there is another direct way.

Answer 1

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

I cannot officially prove this at first, but with night work I find my missing piece. Substitution method with subtraction of the youngest member. Sorry for my bad expression of proof (∵ bad English).

---

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

Assume (suppose) that cφ^n ≦ alg(n) ≦ dφ^n - 2tn for 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 this is correct for n + 1 . By mathematical induction, we can know that it is correct for all n .

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

Answer 2

johnchen902 is correct:

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

but his argument waves his hand a little, so let him become strict. His initial argument was incomplete, so I added mine, but now he has completed the discussion .

---

 loop body = Θ(3n+1) 

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

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

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

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

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

and for n > 3 , we can continue by applying repetition to T(n-2) . For sufficiently large n , therefore, we 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(nk) + ∑ 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 Fibonacci numbers F(n) [ F(0) = 0, F(1) = F(2) = 1 ].

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

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 

Summarizing this, starting with A(2) = 2 = F(5) + F(3) - 5 , we obtain

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

and therefore, for

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

assessment

 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 on the left and right sides of the inequality, Θ(φ^n) , qed

Answer 3

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 alg fails 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 have a division. You should imagine a number tree with N as the 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 

Obviously, there is a pattern of repetition. For each 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 complexity 3k + 1 * (2 ^ (k - 1)) .

I consider the number of repetitions of a pair (n - k, n - k - 1) . So now for every k from 0 to n I have:

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

If you sum this value from 1 to n, you should get the desired result. I will decompose 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, it ends:

 2^n - 1 

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

 3k * 2 ^ (k - 1) 

This is equal to 3 the sum of k = 0, n of k * 2 ^ (k - 1) . This sum can be determined by switching to polynomial functions, integrating, compressing by the formula 1 + a ^ 2 + a ^ 3 + ... + a ^ n , and then differentiating again to get a result that is (n - 1) * 2 ^ n + 1 .

So you have:

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

What is shrinking:

 2 ^ n * (3n - 2); 

Answer 4

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

For this function, the complexity:

  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)

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

g (n) Θ (3 ⁿ )

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