Answer to Question #271980 in Algorithms for Anu

Question

(i) Define a recurrence relation using Divide and Conquer technique and describe its

elements

(ii) Solve the following recurrence relation using Recurrence Tree Method.

T(𝑛) = {1 𝑇(𝑛/2 ) + n

𝑖𝑓 n=1

𝑖𝑓 n> 1

Show all the steps.

Answer 1

i)

Divide

the problem into subproblems that are smaller instances of the same problem.

Conquer

the subproblems by solving them recursively. If the subproblems are small enough, solve them trivially or by "brute force."

Combine

the subproblem solutions to give a solution to the original problem.

Recurrences

The recursive nature of D&C leads to recurrences, or functions defined in terms of:

• one or more base cases, and
• itself, with smaller arguments.

ii)

Step-01:

The given recurrence relation shows-

• A problem of size n will get divided into 2 sub-problems of size n/2.
• Then, each sub-problem of size n/2 will get divided into 2 sub-problems of size n/4 and so on.
• At the bottom most layer, the size of sub-problems will reduce to 1.

The given recurrence relation shows-

• The cost of dividing a problem of size n into its 2 sub-problems and then combining its solution is n.
• The cost of dividing a problem of size n/2 into its 2 sub-problems and then combining its solution is n/2 and so on.

Step-02:

 Determine cost of each level-

• Cost of level-0 = n
• Cost of level-1 = n/2 + n/2 = n
• Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

Step-03:

 Determine total number of levels in the recursion tree-

• Size of sub-problem at level-0 = n/2⁰
• Size of sub-problem at level-1 = n/2¹
• Size of sub-problem at level-2 = n/2²

 Continuing in similar manner, we have-

Size of sub-problem at level-i = n/2ⁱ

Suppose at level-x (last level), size of sub-problem becomes 1. Then:

n / 2^x = 1

2^x = n

Taking log on both sides, we get-

xlog2 = logn

x = log₂n

 ∴ Total number of levels in the recursion tree = log₂n + 1

Step-04:

 Determine number of nodes in the last level-

• Level-0 has 2⁰ nodes i.e. 1 node
• Level-1 has 2¹ nodes i.e. 2 nodes
• Level-2 has 2² nodes i.e. 4 nodes

 Continuing in similar manner, we have-

Level-log₂n has 2^log₂ⁿ nodes i.e. n nodes

Step-05:

 Determine cost of last level-

Cost of last level = n x T(1) = θ(n)

 

Step-06:

 Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic notation:

for n > 1 :

T(n) = = n x log₂n + θ (n)= nlog₂n + θ (n)= θ (nlog₂n)

for n = 1 :

T(1) = θ (1)