Search code examples
algorithmcomplexity-theory

Is it possible for an algorithm's runtime to be defined by two different Big thetha notations?

For an algorithm with a run time of say, the form T(n) = 3n^2+ 2n + 5 I get that there can be multiple Big-O and Omega notations (like O(n^2) and O(n^3) in the given case).

But is it possible for a algorithm to have two Big-Thetha notations describing it? If yes, can you please give an explanation and if not, why not?

In other terms - Is it possible for two different functions to tightly bind the asymptotic running time of an algorithm?

Solution

  • Yes, provided the two "Big-Theta" functions are Big-Theta to each other.

    For example, the running time of Heapsort is both Θ(log n!) and Θ(n log n).