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

Problem Detail: 

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

Asked By : InformedA

Answered By : babou

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29284