Question

Suppose you are choosing between the following two algorithms:

Algorithm A: solves problems of size n by recursively solving two subproblems each of size (n-1) and then combining the solutions in constant time (take T(0) = 0).

Algorithm B: solves problems of size n by recursively solving one subproblem of size (n-1) and then combining the solution in (log n) time (take T(1) = 0).

• Write down the recurrence relations for the above algorithms.                          
• Solve the recurrence relations to find the exact number of operations for each of these two algorithms in terms of (n). Arrange the algorithms in increasing complexity.                

Answer 1

Solution:

Algorithm A:

Given,

=>Solves the problem of size n recuursively solving two subproblems each of size (n-1) and combining the solutions in constant time.

=>T(0) = 0

Explanation:

Recurrence relation:

=>We can write recurrence relation as: T(n) = 2T(n-1) + c where c is some constant.

Solving recurrence relation:

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

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

From (1) and (2)

=>T(n) = 2^2T(n-2) + 2c + c

and so on.

=>T(n) = 2^kT(n-k) + c + 2c + ... + 2^(k-1)c

=>T(n) = 2^kT(n-k) + c*(1 + 2 + 2^2 + .. + 2^(k-1))

Summation of geometric progression.

=>T(n) = 2^kT(n-k) + c*(2^k - 1)...(3)

We know that T(0) = 0

=>n - k = 1

=>k = n...(4)

From (3) and (4)

=>T(n) = 2^n*0 + c*(2^n - 1)

=>T(n) = c*(2^n - 1)

=>Hence T(n) = (2^n)

Algorithm B:

Given,

=>Solves problems of size n by recursively solving one subproblem of size n-1 and then combining solutions in logn time.

=>T(1) = 0

Explanation:

Recurrence relation:

=>We can write the recurrence relation as: T(n) = T(n-1) + logn

Solving recurrence relation:

=>T(n) = T(n-1) + logn....(1)

=>T(n-1) = T(n-2) + log(n-1)...(2)

From (1) and (2)

=>T(n) = T(n-2) + logn + log(n-1)

and so on.

=>T(n) = T(n-k) + logn + log(n-1) + .. + log(n-(k-1))

=>T(n) = T(n-k) + log(n*(n-1)*(n-2)*...*(n-(k-1))....(3)

We know that T(1) = 0

=>n - k = 1

=>k = n-1...(4)

From (3) and (4)

=>T(n) = 0 + log(n*(n-1)*(n-2)*..*(n-(n-1))

=>T(n) = logn!

=>T(n) = nlogn asymptotically

=>Hence T(n) = (nlogn)

Finding order:

=>Algorithm A > Algorithm B because growth rate of algorithm A is exponential and growth rate of algorithm B is combination of polynomial and logarithmic functions.

I have explained each and every part with the help of statements attached to the answer above.