Question

Under what case of Master’s theorem will the recurrence relation of stooge sort fall?

(a) 1

(b) 2

(c) 3

(d) It cannot be solved using master’s theorem

This question was addressed to me during an online interview.

I'd like to ask this question from Masters theorem topic in portion Recursion of Data Structures & Algorithms II

Answer 1

Correct choice is (a) 1

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