Explanation for Drawing Tree With Recursion

Solving Recurrences Using Recursion Tree Method -Determining time Complexity -#1

For the past few weeks I have been reading the introduction to algorithms -the third edition written by Thomas H. Cormen, while reading it section by section I have felt that some math is skipped between the steps, it took me some time to figure out, but it won't always be the same for others, and in future I might need to remember the steps again, so I thought of writing the steps here. In this post I will be showing the steps involved in recursion tree method, if I made a mistake somewhere please feel free to mention it in comments.

CHAPTER 4: RECURSION TREE METHOD FOR SOLVING RECURRENCES

I am going to start this series with recurrence tree method, the given recurrence is

in the given problem a=3, it represents how many subproblems are produced at each level

so we can draw a recursion tree like this ( we need to divide each problem to 3 subdivisions in each step)

from this tree, you can see that the number of subproblems growing at a rate of (3) raised to power i, where is the depth, for example at starting depth

when i = 0, 3⁰ = 1,

when i = 1, 3¹ = 3,

when i = 2, 3² = 9

so the number of subproblems at any i th depth would be 3 raised to the power i

we are going to calculate the cost at each step, so we could draw a recursion tree like this

Noticed cn² at the top tree level? what is it? appeared out of nowhere? :-)

Why the cost is cn²?

Given recurrence is

have a look at the second term,

Θ(n²) represents the following graph ( page number 45)

it tends to fall between c₁g(n) and c₂g(n), in our case g(n) is n², so the bounds are strict , since it lies between limits c₁ and c₂, lets take a constant c, such that f(n) = cn² such that c > n₀

that is the reason the recursion tree uses cn² at the top level, it took me a while to figure it out.

so what are waiting for, we can add the costs and determine the running time of this reccurence ….. Not yet :-) , we need to determine some other factors before adding the running time at each step.

the only thing to determine before adding the time taken at each steps is to find the time taken at last step. in the book after skipping some math it is given as

for me it didn't make any sense at the first look, therefore i have tried to find what was done before this term arrived.before jumping in to that calculation, let me make a gentle remainder

3 -number of subproblems at each step

16 -factor in which n gets divided at every step (a little bit confusing at this stage, ignore this if you didn't understand, it will be clear at the end of this article)

i is the depth of the recursion i ∈ 0,1,2…h , can you guess what might be the depth when the recursion reaches its bottom?(h represents the bottom depth level)

we have another factor getting affected when the problem reaches the bottom condition, the subproblem size, yep you guessed it right. When you touch the bottom or boundary condition the subproblem size tends to be 1, you may notice at step 0, size = n

step 1, size = n / 16

step 2, size = n²/ 256, or n²/16²

at any step i , size = n/4ⁱ (equation 1)

we know the fact that when it hits the boundary condition, size tends to be 1

substituting in equation 1 we can get the following equation

we solve this equation by two methods ( choose which one is easy for you), the aim is to find the depth where the recurrence will eventually reach the boundary condition.

METHOD 1

METHOD 2 (TAKING LOG ON BOTH SIDES)

So we found the boundary depth would be log₄ n , this is the depth our recurrence stops, so our depth would range from 0,1,2, ….. log₄ n

ADDING ALL THE COSTS FROM DEPTH 0 TO log₄ n

whoa, how does this equation appear out of nowhere?, here we go again

at depth 0 , cost = cn²

at depth 1 cost = 3 * c(n/4)² ( 3 represents the number of subproblems at that node) (solving this will give the second term)

at depth 2 cost = 3 * c(n/16)² (notice subproblems get increased exponentially by factor of 4 )

at depth n-1 cost (just a term before the last term, we have a constant value for last term, that is the reason we find this term here)

depth n-1 cost = 3 *c(n/16)^(log₄ n -1)

last level, ie boundary level cost =

so we find that n ^ ( log₄ n³) subproblems are present in the last depth. the time required to compute them would be T(1), we assume that as a constant, that's how we get sum equation like this

the explanation for the second step would be unnecessary, but still, this derivation is incomplete, we need to derive a quadratic polynomial from this equation, we need set the upper bound as infinity, so T(n) would be definitely lesser than the assumed upper bound.

at the end, the term (16/13) cn² clearly indicates the recurrence has an upper bound of O(n²)

This series will be continued…

townsendslesintsend.blogspot.com

Source: https://medium.datadriveninvestor.com/solving-recurrences-using-recursion-tree-method-determining-time-complexity-5e327c82e4d5

Share this post