Sorting

Question 1

Master theorum for T(n) = aT(n/b) + f(n)

Answer 1

if f(n) = theta(n^d), where d >= 0,
T(n) = theta(n^d) if a < b^d
T(n) = theta(n^d logn) if a = b^d
T(n) = theta(n^log b a) if a > b^d