StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Big O is giving only upper asymptotic bound, while big Theta is also giving a lower bound.</p> <p>Everything that is <code>Theta(f(n))</code> is also <code>O(f(n))</code>, but not the other way around. <br><code>T(n)</code> is said to be <code>Theta(f(n))</code>, if it is both <code>O(f(n))</code> <strong>and</strong> <code>Omega(f(n))</code></p> <p>For this reason <strong>big-Theta is more informative then big-O</strong> notation, so if we can say something is big-Theta, it's usually preferred. However, it is harder to prove something is big Theta, than to prove it is big-O.</p> <p>For <strong>example</strong>, <a href="http://en.wikipedia.org/wiki/Merge_sort" rel="noreferrer">merge sort</a> is both <code>O(n*log(n))</code> and <code>Theta(n*log(n))</code>, but it is also O(n<sup>2</sup>), since n<sup>2</sup> is asymptotically "bigger" than it. However, it is NOT Theta(n<sup>2</sup>), Since the algorithm is NOT Omega(n<sup>2</sup>).</p> <hr> <p><code>Omega(n)</code> is <em>asymptotic lower bound</em>. If <code>T(n)</code> is <code>Omega(f(n))</code>, it means that from a certain <code>n0</code>, there is a constant <code>C1</code> such that <code>T(n) >= C1 * f(n)</code>. Whereas big-O says there is a constant <code>C2</code> such that <code>T(n) <= C2 * f(n))</code>.</p> <p>All three (Omega, O, Theta) give only <em>asymptotic information</em> ("for large input"):</p> <ul> <li>Big O gives upper bound</li> <li>Big Omega gives lower bound and</li> <li>Big Theta gives both lower and upper bounds</li> </ul> <p>Note that this notation is <strong>not</strong> related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload