I finally thought I understood what it means when a function f(n)
is sandwiched between a lower and upper bound which are the same class and so can be described as theta(n).
As an example:
f(n) = 2n + 3
1n <= 2n + 3 <= 5n for all values of n >= 1
In the example above it made perfect sense, the order of n is on both sides, so f(n)
is sandwiched between 1 * g(n)
and 5 * g(n)
.
It was also a lot clearer when I tried not to use the notations to think about best or worst case and instead as an upper, lower or average bound.
So now thinking I finally understood this and the maths around it I went back to visit this page: https://www.bigocheatsheet.com/ to look at the run times of various search functions and was suddenly confused again about how many of the algorithms there, for example bubble sort, do not have the same order on both sides (upper and lower bound) yet theta is used to describe them.
Bubble sort has Ω(n)
and O(n^2)
but the theta value is given as Θ(n^2)
. How is that it can have Θ(n^2)
if the upper bound of the function is in the order of N^2
but the lower bound of the function is in the order of n
?
Actually, the page you referred to is highly misleading - even if not completely wrong. If you analyze the complexity of an algorithm, you first have to specify the scenario: i.e. whether you are talking about worst-case (the default case), average case or best-case. For each of the three scenarios, you can then give a lower bound (Ω), upper bound (O) or a tight bound (Θ).
Take insertion sort as an example. While the page is, strictly speaking, correct in that the best case is Ω(n), it could just as well (and more precisely) have said that the best case is Θ(n). Similarly, the worst case is indeed O(n²) as stated on that page (as well as Ω(n²) or Ω(n) or O(n³)), but more precisely it's Θ(n²).
Using Ω to always denote the best case and O to always denote the worst-case is, unfortunately, an often made mistake. Takeaway message: the scenario (worst, average, best) and the type of the bound (upper, lower, tight) are two independent dimensions.