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