Monday, 12 November 2012

The Master of all theorems : "The Master Theorem" ?

Clearly, the theorem was given the title for a reason. It was made to make everyone's lives just a little bit easier when finding time complexity of an algorithm without doing all the messy unwinding.. 
I studied it over and over, I knew how to use the Master Theorem, walked in to the write Test 2, saw Master Theorem question.... Perfection! ..or so it thought. What do I end up doing? Unwinding T(n) before applying the Masters Theorem!!!! >.< 
I should just slap my self over and over and over and over again.. and more. *Sigh*

I remembered to write what P(n) this time though! Life lessons I'll say.

So, to make up for my mistake,  Here goes..

The Masters Theorem: 

For T(n) =  aT( n/b ) + f(n) 

T(n)  =     Θ (nd)    if a < bd
         =     Θ (nd log n)    if a = bd
        =     Θ (nlogb a )      if a > bd


where a is the number of recursions, b is how many parts we divide n in to  and finally d is the largest degree of the polynomial f(n)

So, if i was given  lets say --- T(n) = T(⌈n/2⌉)+ T(⌊n/2⌋) +  1

If n was a power of 2,  we can simplify T(n) to be: T(n) = 2T(n/2) +  1

Now,  it's visible that a = 2, b = 2 and d = 0 since the largest degree of 1 is 0.
With this information, and the use of the Master Theorem, the complexity time of T(n) would be : 
Θ ( nlogb a )  since 2 > 20 

Finally,

T(n) = Θ( nlogb a )
T(n) = Θ( nlog2 2  )  =  Θ( n )

Phew! There, done. 

No comments:

Post a Comment