You are misunderstanding O vs. Theta.

[umanwizard]

You seem to be making the common mistake of thinking big-Theta means average case and big-O means worst case, which is not correct.

Either big-O or big-Theta or big-Omega can be used meaningfully to describe any of best, average, or worst case -- the concepts are completely orthogonal.

To be mathematically accurate your page should have Theta everywhere.

[ethangodt]

Came here to say this. Easy to misunderstand it. 👍

[mtheos]

Can you elaborate for us common folk?

[ethangodt]

@mtheos these exercises on Khan Academy explain it well https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

The gist is that O, Theta, and Omega are different sets of mathematical “bounds”. O is an upper bound only, Theta is an upper and lower bound, and Omega is a lower bound only.

You can put upper and lower bounds on anything, including the average and best cases of an algorithm. The Big O (upper bound) of a best case linear search is O(1). The Big O of a worst case linear search is O(n). Notice for best case I did not use Omega. Upper bound does not mean worst case, it is mathematical concept simply meaning some line that (when the inputs are large enough) will always be above or equal to the line it’s a bound over.

[ranggakd]

source