I've been stuck for hours trying to solve the recurrence $T(n) = 7T(n/3) + n^2 + 2n$ by using case 3 of the master theorem.

I've done a good chunk of the proof, but currently stuck attempting to solve the regularity property $af(n/b) \leq cf(n)$.

I don't think this fits the case 3 requirements, but my best shot has been $(7n^2 / 9) + (14n / 3) \leq (7/9)n^2 + 2(14/3)n$. This is true for all $n$, but I'm using 2 constants. What should I do to find the sole constant $c$ (where $c$ is $0 < c < 1$) which would satisfy case 3?

  • 3
    $\begingroup$ Just ignore the $+ 2n$, and you have $a=7$, $b=3$, and $d=2$. $\endgroup$
    – Pål GD
    Commented Oct 5, 2023 at 13:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.