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

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

• "I know that Big O is used to bound worst case running time." -- while not wrong, it's not the whole truth. I recommend you check out our reference questions on asymptotics; I think all the answers you need are there. – Raphael Aug 21 '14 at 10:11
• The use of the $\Theta$-notation for "overall complexity", i.e. considering all computation over all inputs of a given size $n$, may be meaningless. But it is always meaningful for worst case and best case complexity. See my answer. – babou Aug 21 '14 at 11:26
• @Raphael I should have used the reference questions to answer. But I am used to the Landau page. – babou Aug 21 '14 at 12:23

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.

• I think the OP understands the Landau notation. – john_leo Aug 21 '14 at 9:07
• @john_leo Then I do not understand what he is asking. Big O is for upperbounds. He refers to it explicitly, but is looking for lower bounds ... and does not mention Big $\Omega$. – babou Aug 21 '14 at 9:12
• I think he's asking for the term you use when you have a concrete example that needs the precise upper bound you claim. – john_leo Aug 21 '14 at 9:16
• @john_leo thank you. I want to know the notation used when there is an example that make the bound happens. I believe $\Theta$ is what I am after, but I have seen confusing comments so I want to ask for advice from the experts. – InformedA Aug 21 '14 at 9:18
• @randomA FrankW's answer is a lot better than what I would have said, so go with his. – john_leo Aug 21 '14 at 9:40

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.
• Ok, this is really a wording problem now. It has been a habit at school that when one talks about runtime, we implicitly refer to worst case runtime unless specified otherwise. – InformedA Aug 21 '14 at 9:40
• What is an instance of quicksort ? [cc @randomA ] – babou Aug 21 '14 at 9:53
• Being word by word correct, from your last point, worst case running time for bubble sort is $\Theta(n^2)$ would be a correct statement. Correct? – InformedA Aug 21 '14 at 9:54
• @babou I would implicitly understand it as an input instance for quicksort – InformedA Aug 21 '14 at 9:54
• @randomA An input instance of what size ? :) – babou Aug 21 '14 at 9:56

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

• "Use the notation that expresses the strongest property you know to be true." -- And never make this an implicit assumption/convention. – Raphael Aug 21 '14 at 21:21