Question

What is the recurrence relation for stooge sort?

(a) T(n) = 2T(2/3n) + O(n)

(b) T(n) = 2T(2/3n) + O(1)

(c) T(n) = 3T(2/3n) + O(n)

(d) T(n) = 3T(2/3n) + O(1)

The question was posed to me in an international level competition.

The question is from Sorting topic in division Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (d) T(n) = 3T(2/3n) + O(1)

The best explanation: In stooge sort recursion is applied to 2/3 part of the array 3 times. Rest of the portion of code has a constant time complexity. So the overall recurrence relation becomes T(n) = 3T(2/3n) + O(1).