Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
"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 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 at 11:26
    
@Raphael I should have used the reference questions to answer. But I am used to the Landau page. –  babou Aug 21 at 12:23

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
I think the OP understands the Landau notation. –  john_leo Aug 21 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 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 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. –  randomA Aug 21 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 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.
share|improve this answer
    
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. –  randomA Aug 21 at 9:40
    
What is an instance of quicksort ? [cc @randomA ] –  babou Aug 21 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? –  randomA Aug 21 at 9:54
    
@babou I would implicitly understand it as an input instance for quicksort –  randomA Aug 21 at 9:54
    
@randomA An input instance of what size ? :) –  babou Aug 21 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)$.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.