CODEWITHSUNDEEP
algorithmdivide-and-conquerrecurrencemaster-theorem
Ondrej Skopek
Ondrej Skopek

Reputation: 798

Master Theorem Case 3 Example Algorithms

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?

Upvotes: 1

Views: 916

Answers (1)

btilly
btilly

Reputation: 46409

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.

Upvotes: 1

Related Questions