What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

Question

I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically.

Similarly, one can say that for example merge sort's running time is $O(n^2)$ which is correct. But we know that there is a better bound for it: $O(n\log n)$. Technically speaking, one can say that every polytime algorithm has running time $O(2^n)$. This is correct, but not useful.

So my question is: what is the notation used for the case of worst case running time such that there exists an input in which the worst case running time happens.

In the merge sort example, one cannot construct an input example so that merge sort would take $n^2$ comparisons, but one can construct an example that requires the number of comparisons being about $n\log n$.

Answer 1

See "big 0" or Landau notation in wikipedia. What you are looking for is the section on Bachmann-Landau notations.

• $f(n)\in O(g(n))$ means $f$ is bounded above by $g$ up to a constant.

• $f(n)\in \Omega(g(n))$ means $f$ is bounded below by $g$ up to a constant.

• $f(n)\in \Theta(g(n))$ means $f(n)\in O(g(n)) \wedge f(n)\in \Omega(g(n))$

Further remarks (since the scope of the question is being implicitely extended)

These definitions can be used for worst case as well for a best case analysis of complexity, starting from an analysis of respectively the greatest or least costs over all inputs of size $n$.

Then, for algorithm $A$, let $A_{min}(n)$ and $A_{max}(n)$ be respectively the best case and worst case complexity of $A$.

Then, omitting intentionally "worst case" or "best case". so as to cover all cases, you can say that:

• the complexity of $A$ is $O(g(n)$ iff $A_{max}(n)\in O(g(n)$

• the complexity of $A$ is $\Omega(g(n)$ iff $A_{min}(n)\in \Omega(g(n)$

Now using the $\Theta$-notation is not necessarily meaningful for this "overall" complexity of $A$. It is meaningful iff $O(A_{max}(n))=O(A_{min}(n))$

To be complete, many people also use average case analysis.

Also, people often mean worst case when they omit qualification of the complexity.

Answer 2

In words, such a bound is called a tight bound. In the specific case of Landau notation, $\Theta$ can be used to indicate a tight bound. You have to be somewhat careful about your wording, though:

• "The runtime of quicksort is in $O(n^2)$," is a correct statement (but somewhat imprecise).
• "The runtime of quicksort is in $O(n^2)$, and this bound is tight," is correct and expresses, what you want to express.
• "The worst-case runtime of quicksort is in $\Theta(n^2)$," is equivalent to the previous statement.
• But "The runtime of quicksort is in $\Theta(n^2)$," is not correct, since this statement implies that quicksort takes quadratic time on every input.

Answer 3

Use the notation that expresses the strongest property you know to be true.

Suppose you have an algorithm.

• If you have a class of inputs on which the algorithm runs in time $O(f(n))$, this actually tells you nothing about the worst-case running time: the worst case is worse than something that's better than $f(n)$, which could be literally anything.

• If you have a class of inputs on which the algorithm runs in time $\Omega(f(n))$ or $\Theta(f(n))$, then you know that the worst case running time is at least as bad as this class, so the worst case is $\Omega(f(n))$.

• If you have a class of inputs which you know to be the worst case, and the algorithm runs in time $O(f(n))$, $\Omega(f(n))$ or $\Theta(f(n))$, they you know that the worst-case running time is $O(f(n))$, $\Omega(f(n))$ or $\Theta(f(n))$, respectively.

In the merge sort example, one cannot construct an input example so that merge sort would take $n^2$ comparisons, but one can construct an example that requires the number of comparisons being about $n\log n$.

This falls into the third bullet: you have a class of inputs which you know to be the worst case, and the algorithm takes time $\Theta(n\log n)$ on those inputs. So the worst-case running time is exactly that: $\Theta(n\log n)$.