Can I use Θ if tightest lower and upper bound are not the same?

Question

When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation? If an algorithm has a running time of $\Theta(n)$, is it safe to assume that the upper and lower bound are the same?

Answer 1

When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation?

Do you mean to say that we can only prove an $\Omega(f_1)$ and an $O(f_2)$ bound, respectively, on the same cost function (such as "worst-case running time)? Then yes: you can only use $\Theta(f_1) = \Theta(f_2)$ to combine the bounds if, well, $f_1 \in \Theta(f_2)$.

If you mean to say that best case and worst case have different growth rates, then that's a different issue: "lower bound" and "best case" as well as "upper bound" and "worst case" are not the same concepts! You can have $\Theta$-bounds for either case, but they still don't combine in a meaningful way since they are talking about different cost functions.

Also, if an algorithm has a running time of theta(n), is it safe to assume that the upper and lower bound are the same?

That's not a "safe assumption", that's the definition of $\Theta$.

I suggest you revisit the definitions of the different Landau symbols and the basics on how to use them in algorithm analysis. Maybe start reading at our reference question.

Answer 2

Often when describing running times of algorithms we leave out information that can usually be inferred. Typically you should include: Time Complexity (Landau Notation), Input Type (worst case, best case, average, etc.) and Machine Model (e.g. RAM). The last two are often inferred, but you should describe them in your case.

I suspect when you say "the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same", what you really mean is "the asymptotic running time in the best case is not the same as the asymptotic running time in the worst case".

Imagine a simple function like this:

$$f(n) = c + n\cdot (n \bmod 2)$$

We can say the following:

• $f(n) = O(n)$
• $f(n) = \Omega(1)$

However, we could not concretely give a $\Theta(?)$ bound without more context. It would be more proper to say:

• $f(n) = \Theta(n)$ in the worst case (or $f(n) = O(n)$ in the worst case)
• $f(n) = \Theta(1)$ in the best case (or $f(n) = \Omega(n)$ in the best case)

The former of each statement is more precise and doesn't leave much room for error. The latter would also work but isn't as strict of an argument. I think this answer gives a good distinction on why a descriptive $\Theta(\cdot)$ should be preferred to an ambiguous $O(\cdot)$ or $\Omega(\cdot)$.

Answer 3

f(n) = ϴ(g(n)), if and only if:

• f(n) = O(g(n)) (at the worst case f(n) performs an asymptotically equivalent of g(n) operations); and
• f(n) = Ω(g(n)) (at the best case f(n) performs an asymptotically equivalent of g(n) operations)

So the answer to your second question is straightforward - yes, as it is the actual definition of the theta notation.

Regarding your first question, it would be inaccurate to denote the running time of such an algorithm in theta notation. In some cases, though, an algorithm may approximately perform as if it was bounded by a theta notation (meaning that only in extreme situations it performs otherwise). Still, you can't use the theta notation, unless your algorithm satisfies both conditions mentioned above.