+1 vote
27 views

When analyzing a recurrence of the form T(n) = a T(nb) + θ(nc), under which of the following conditions can we conclude that “most of the work occurs at the leaves of the recursion tree”?

1.   c <loga
2.   c = logb a
3.   c > logb a
4.   None of these