CODEWITHSUNDEEP
asymptotic-complexityrecurrencemaster-theorem
Nulle
Nulle

Reputation: 1329

Why does the Master Theorem only return Theta?

Looking at the three cases of the Master Theorem for Recurrences. Then it always returns a theta.

This makes me wonder does that mean it can only find the running time of functions having a theta?

If yes is it then the constraints a>=1 and b>1 that ensures the recurrence has a theta at all?

For an example the recurrence of Mergesort the Master theorem can be used but for the recurrence of Quicksort it can't since Quicksort does not have a theta but only an Omega and big O that varies. Is this how it is?

Upvotes: 0

Views: 3240

Answers (1)

AbcAeffchen
AbcAeffchen

Reputation: 14987

The Master Theorem just tells you the complexity of a recurrence of the form T(n) = a * T(n/b) + f(n). This has nothing to do with an algorithm. It is just a mathematical expression and you can exactly evaluate it, if you know a, b and f. So it also has an exact complexity denoted by Θ.

Also "functions having a theta" doesn't make that much sense. Functions/algorithms have complexities and this complexities can be expressed in terms of one or more input parameters. You can analyze many different complexities for every algorithm: worst case, best case, average case, smoothed complexity and maybe more. These complexities can have upper and lower bounds and sometimes upper and lower bound are the same. This bounds can be simplified using the big-O notation.

So to translate this to your Quicksort example:
It has a worst case of O(n²) and a best case of Ω(n log n) and an average case of Θ(n log n) (if you choose you pivot the right way).

Upvotes: 3

Related Questions