Master Theorem Case 3 Example Algorithms

759 views Asked by At

While learning the Master theorem I'm having trouble coming up with a real-world algorithm as an example, whose recurrence strategy would fall into Case 3. Can you suggest any links where I can read more about such algorithms?

1

There are 1 answers

1
btilly On BEST ANSWER

Case 3 arises when the effort of doing the first recursive step is comparable to the work for all of the others. The quickselect algorithm for finding the median value in an array is a good example.