Question

2. In class, we learned that the running time of Karatsuba’s algorithm can be expressed as the recurrence T (n) = 3T (n/2) + n. We then used the substitution method to solve the recurrence.

   When using the substitution method, it seems difficult to make a guess about the upper bound on the running time. However, if we use the recursion tree method, it would be a lot easier.

   In this question, you are asked to solve this recurrence using the recursion tree ap- proach, which can be further used to help us make the guess (you are not required to explain how to make use of your result to make the guess; only show your work using the recursion tree). You can assume that T(1) = 1 and that n is a power of 2 for convenience. Give your solution using big-Oh notation.

Answer 1

Given Recursion :

T(n) = 3T(n/2)+n

Recursion solution using Tree Approach:

So basically,if we draw out the recursion tree then we will find that,

the number of level's in the recursion tree will be as

h=log_2⁡n+1 , where h = height of the tree

and the number of leave's in the recursion tree will be

3^ℎ−1= 3^log₂(?) [h = log_2⁡n+1 ]

= ?^log₂3

Now we will be able write the time formula as the foloowing:

T(n) = cn + c(3n/2) + c(9n/4) + ......+ cn(3^h-2 / 2(h-2)) + Θ(?^log₂3)

Explanation:

  

So we will be able to solve this using Masters theorem, but also we can solve by creating the recursion tree in the following way as given below:

1. At the top of  the root of the recursion tree which we created ,we  will be have a work of n.

2. In the second step or we can say that in  the second stage, the recursion tree splits into three parts / division's, and in each part, the work will be n / 2.

3. We will Keep going until we will reach out to the leaves of the recursion tree and the entire work leaf will be:

O (1) = O (n / 2 ^k)

when: n = 2 ^k

4. we know that at each / every step m have 3 ^m splits / parts further in the recrsion tress.

5. Now we will  combine all the steps together by using the geometric progression and logarithms rules.

and by solving the below equation which we obtained as below

T(n) = cn + c(3n/2) + c(9n/4) + ......+ cn(3^h-2 / 2(h-2)) + Θ(?^log₂3)

It will give the Time complexity as:

?(?)=Θ(?^log₂3)