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

Question

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?

please read this: https://stackoverflow.com/a/12338937/6129793 — Peter, Jul 22 '20 at 14:14
Constant factors don't matter, so Theta(f(n)) and Theta(5*f(n)) would be two different expressions (but they mean basically the same). — Henry, Jul 22 '20 at 14:17
Hi, Ik what the different notations represent, probably my question is more mathematical, I wanna know if its possible for a function to have two different functions that tightly bind its running time — Ayush, Jul 22 '20 at 14:17

score 1 · Accepted Answer · answered Jul 22 '20 at 14:17

1

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).

answered Jul 22 '20 at 14:17

Yves Daoust

53,540
8
41
94

Ah that seems to make some sense but how does that wrap out, I mean how are "log n" and "n log n" Big-theta to each other? – Ayush Jul 22 '20 at 14:22
@Ayush: log n! . – Yves Daoust Jul 22 '20 at 14:22
Ah right, my bad, but still I dont get how they both are big-theta to each other :( – Ayush Jul 22 '20 at 14:24
@Ayush: any idea of the asymptotic behavior of log n! ? – Yves Daoust Jul 22 '20 at 14:25
Sorry, no! Is there a simpler example? – Ayush Jul 22 '20 at 14:27
Another example would be two different polynomials with the same high order term. In fact Theta(f(n)) is a set of functions. You can use any member as representative. – Henry Jul 22 '20 at 14:30
@Ayush: `Tn` (n-th triangular number) and `n²`. – Yves Daoust Jul 22 '20 at 14:31
1

@Ayush See https://en.wikipedia.org/wiki/Stirling%27s_approximation for the behavior of `log(n!)`. Basically `log(n!) = n log(n) - n + O(log(n))`. From a Big-theta perspective, all that matters is the leading `n log(n)`. – btilly Jul 22 '20 at 15:50

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

1 Answers1