HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is Big-Theta a more accurate description of worst case run time than Big-O?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thetacasedescriptionthanmoretimebigaccurateworstrun

Problem

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"

To me, the only difference is that when we say $O(n^2)$, the function may also be $O(n)$, we do not know. But when we say $\Theta(n^2)$, we know for a fact the function is $O(n^2)$ and $\Omega(n^2)$, because it is bounded by $c_1n^2\leq f(n)\leq c_2n^2$ (correct me if I am wrong).

Therefore, can we not say that $\Theta(n^2)$ gives us a more accurate (or at least equal) sense of worst-case run time than $O(n^2)$?

Solution

O(f(n)) is also used when there is no simple function that your runtime is close to. For example: Find the smallest prime factor of n by trial division, finishing when a factor is found: There are O(n^1/2) tests if you divide by all integers up to the square root of n. But for even n there is only one test, and similar if n has any small factor.

So you can’t give any reasonable Theta unless you say f(n) = Theta(f(n)) which is true but pointless.

There is also the possibility that I can prove that a function is for example $O(n^2)$. I may suspect it is actually smaller, it may actually be $O(n)$ but I cannot prove it. Obviously in that situation I can also not prove that it is $\Theta(n^2)$ - because it isn't true.

Context

StackExchange Computer Science Q#154107, answer score: 8

Revisions (0)

No revisions yet.