Recurrence relation

[agnitrate]

Thanks to anybody who even reads this, let alone helps.

I'm having the hardest time solve this recurrence relation. Admittedly, I've never been very good at them. Maybe somebody can see what I'm doing wrong.

I'm supposed to prove the relation is O( n * log^2 n ). This is somewhat ambiguous since I'm not sure if it's n * log( log n ) or n* (log n)^2. Anyways, here's what I get :

T(n) = 4 * T( floor(n/4) ) + 12*n*log n; T(4) = 4;

T(n) = 4 * ( 4 * T( floor(n/16) ) + 12 * (n/4) * log( n/4 ) ) + 12*n*log n
T(n) = 16 T( floor(n/16)) + 12*log(n/4) + 12*n*log n //after simplification

T(n) = 16 ( 4 * T( floor(n/64) + 12*(n/16) * log(n/16)) + 12*log(n/4) + 12*n*log n
T(n) = 64 T( floor(n/64)) + 12*log(n/16) + 12*log(n/4) + 12*n*log n

T(n) = 4^k T( floor(n/(4^k)) + 12*n( log(n/(4^(k-1)) + log(n/4^(k-2)) + ... + log(n) )

T(n) = 4^( log base 4 of n ) + 12*n*( log(n/(4^(k-1)) + log(n/4^(k-2)) + ... + log(n) )

I attempt to simplify all of this and get :

T(n) = n + 12*n*( huge mess )

This doesn't appear to be O( n * log^2 n ) at all. I can get it to be somewhat linear but not logarithmic. Suggestions?

-silver

 

[Legendary]

I can't help you, but the O you're looking for is:
O(n*(log(n))^2)
since you didn't seem too sure about what you were looking for.

 

[agnitrate]

bump for the night crowd. Thanks for the clarification Legendary.

-silver