Recurrences
June 18th, 2023
Solve the recurrence T(n) = 2T(sqrt(n)) + 1 by making change of variables. The solution should be asymptotically tight.
2. Use a recursive tree to give an asymptotically tight solution to the recurrence T(n) = T(n-a) + T(a) + cn, where n > = 1 and c > 0 are constants.