Question

What is the average time complexity of stooge sort?

(a) O(n^2)

(b) O(n^3)

(c) O(n^2.6)

(d) O(n^2.7)

The question was posed to me during an internship interview.

I'd like to ask this question from Sorting in division Sorting of Data Structures & Algorithms II

Answer 1

The correct answer is (d) O(n^2.7)

Easiest explanation - The recurrence relation of stooge sort is given as T(n) = 3T(2/3n) + O(1). It is found to be equal to O(n^2.7) using the master’s theorem.