Skip to main content

New answers tagged

1 vote

Recurrence Upper Bound Estimation

The guess $T(n) \le cn^2\lg n$ does not work. Suppose it does, then we need to show the following: \begin{aligned} 4c(n/2)^2\lg(n/2) + n^2\lg n & \le cn^2\lg n\\ \implies (c+1)n^2\lg n - cn^2 &...
codeR's user avatar
  • 1,273

Top 50 recent answers are included