PS4 Solutions
- Problem 1:
foo(N) = T(N) = T(N-1)
bar(N) = T(N) = (N-1)*T(N-1)
bazo(N) = T(N) = N2*O(N2)*T(N/2)
hard(N) = T(N) = T(N/2)+T(N-1)
- Problem 2:
easy(N) = T(N) = 4*T(N/3) +O(N2)
using Theorem 7.5
A= 4, B=3, k=2
T(N) = O(N2)
Jose M. Vidal
Last modified: Thu Sep 23 11:16:42 EDT 1999