# 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. Aug 21, 2014 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. Aug 21, 2014 at 11:26
• @Raphael I should have used the reference questions to answer. But I am used to the Landau page. Aug 21, 2014 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. Aug 21, 2014 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$. Aug 21, 2014 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. Aug 21, 2014 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. Aug 21, 2014 at 9:18
• @randomA FrankW's answer is a lot better than what I would have said, so go with his. Aug 21, 2014 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. Aug 21, 2014 at 9:40
• What is an instance of quicksort ? [cc @randomA ] Aug 21, 2014 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? Aug 21, 2014 at 9:54
• @babou I would implicitly understand it as an input instance for quicksort Aug 21, 2014 at 9:54
• @randomA An input instance of what size ? :) Aug 21, 2014 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. Aug 21, 2014 at 21:21