Admin: Admin moved page Theta versus Big O to Theta vs Big O

2017-06-27T04:39:41Z

Admin moved page Theta versus Big O to Theta vs Big O

← Older revision	Revision as of 04:39, 27 June 2017
(No difference)

Admin: Created page with "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 ad..."

2017-06-27T04:17:40Z

Created page with "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 ad..."

New page

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

[[Category:Algorithms]]
[[Category:CS]]
{{CSFlag}}

Theta vs Big O - Revision history

Admin: Admin moved page Theta versus Big O to Theta vs Big O

Admin: Created page with "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 ad..."