Awesome q2a theme
+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

in Algorithms by (11 points)
reshown by | 80 views

1 Answer

+7 votes
Best answer

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 by
+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!
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,437 questions
2,714 answers
13,238 comments
95,460 users