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.
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).
Computer Sciencenotes on computer science topics on the wiki, for educational and learning purposes
Part of the 2017 CS Study Plan.
Flags · Template:CSFlag · e