White RoomNEW White Room DSA

Where The Log Vanishes

A candidate solves T(n)=4T(n/2)+nlgnT(n) = 4T(n/2) + n \lg n by saying: "master theorem case 2, so T(n)=Θ(nlog24lgn)=Θ(n2lgn)T(n) = \Theta(n^{\log_2 4} \lg n) = \Theta(n^2 \lg n)."

Compare f(n)=nlgnf(n) = n \lg n against nlogba=n2n^{\log_b a} = n^2 and give the correct answer.