From charlesreid1

(Redirected from Theta versus 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: