+1 vote
80 views

How to find the complexity of this using masters theorem or induction

T(n) = 3T(n/12) +T (n/4) +n

reshown | 80 views

Master theorem can be used to find the complexity of recurrences of forms:

• $T(n)=aT(\frac{n}{b}) + f(n)$
• $T(n)=aT(n-b) + f(n)$

Since the given equation is not in any of the above forms master theorem cannot be used, we can use recurrence tree method to calculate complexity.

As mentioned here, in recurrence tree method, we draw a recurrence tree and calculate the time taken by every level of tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from the given recurrence and keep drawing till we find a pattern among levels. The pattern is typically a arithmetic or geometric series.

For $T(n)=3T(n/12)+T(n/4)+n$, the combine time is O(n), so this can be broken down as:

For level 0, the time will be $=n$               $\dots Level\ 0$

n                                                                  //Level 0

/                           /                          \                          \

T(n/12)                   T(n/12)                 T(n/12)             T(n/4)                 //Level 1

For level 1, time will be

$=3*(\text{combine time of}\ T(n/12)) + (\text{combine time of}\ T(n/4))$

$= 3*n/12 + n/4$

$= n/4 + n/4$

$= n/2$                                                      $\dots Level\ 1$

This tree can be further broken down as:

n

/                                        /           \                                  \

T(n/12)                              T(n/12)    T(n/12)                      T(n/4)

/                /                  \                 \                                          /            /               \                \

T(n/12*12)  T(n/12*12)  T(n/12*12)  T(n/12*4)           T(n/4*12) T(n/4*12) T(n/4*12) T(n/4*4)

From level 2 the time for leftmost part, i.e. sub tree of $T(n/12)$

$= 3*n/12*12 + n/12*4$

$= n/12*4+n/12*4$

$=n/12*2 \ \ \ \dots \dots \dots (T_1)$

and the time for rightmost part, i.e. sub tree of $T(n/4)$

$= 3*n/12*4 + n/4*4$

$= n/4*4+n/4*4$

$=n/4*2\ \ \ \ \dots \dots \dots (T_2)$

Clearly, for level 2, the sub tree for T(n/12) will be considered thrice and T(n/4) will be considered once, so the total time for level 2 will be:

$3*T_1 + T_2$

$=3*n/12*2 + n/4*2$

$=n/4*2+n/4*2$

$=n/4$                                                        $\dots Level\ 2$

Now,

$T(n) = \text{Sum of time for all the levels}$

$=O(n+n/2+n/4+\dots \dots)$

This is an infinite GP with ratio $1/2$ and first term $n$, hence

$T(n)=O(n/(1-\frac{1}{2}))=O(n/\frac{1}{2})=O(n)$

by (855 points)
selected
+1
Great job dude!
+1

Bro, one correction,

This is an infinite GP with ratio n/2 and first term n, hence

It’s common ratio is ½.

+3
Thanks for notifying, I’ve updated the answer.
0
Can you tell me about Master’s theorem on:

$T(n)=aT(n−b)+f(n)$

I only read about the $a*T(n/b)$ one. Just provide me some link, if possible.
+2

For this version, it is necessary that $f(n)$ must be a polynomial. Let the degree of $f(n)$ be $k$. We have $3$ cases based on the value of $a$:

• If $a<1: T(n)=O(n^k)$
• If $a=1: T(n)=O(n^{k+1})$
• If $a>1 : T(n)=O(n^k*a^\frac{n}{b})$
0
Thanks. Got it!