Theta vs Big O

One of the things that you'll notice as you peruse algorithm and data structure textbooks is that there tend to be two camps: the Big O camp, and the Theta camp.

This page addresses some of the reasons why you would use one versus the other.

Why Big O

This is the more common concept, and is used because it is often easier to intuit about. The big O complexity class refers to an upper bound on the cost of the algorithm. It's a coarser and less rigorous way of comparing algorithms.

This is the approach you see in most textbooks, undergraduate material, etc.

Why Theta

Theta is a lower bound - a big-Theta cost of T(f(n)) says you can never do better than f(n) in terms of cost. This is a way of talking about the cost of the absolute best your algorithm will be able to do.

MIT lecturers often make use of Theta(n).

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag