About this document

Asymptotic Analysis of Recurrences by Anuj Mathew is a document available to read on EtoBox.

This document contains solutions to recurrence relation problems. It first shows that the recurrence T(n) = T(n-1) + n has a solution of Θ(n^2) using induction. It then shows that the recurrence T(n) = T(⌈n/2⌉) + 1 has a solution of O(lg n). Finally, it uses the master method to derive tight bounds for several recurrences: i) T(n) = 2T(n/4) + 1 is Θ(sqrt(n)), ii) T(n) = 2T(n/4) + sqrt(n) is Θ(sqrt(n)lg n),

Author

Anuj Mathew

Language

EN