That page says o(f) == O(f) and not Theta(f). When you say "small-o is a claim that your process can't be faster than -this-", that seems to match the definition of Omega(f). Did you mean that the author should have used big-Omega?
As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
>As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g).
Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
For equality, yes, Theta works! But I care not just about equality but about comparison. In particular, it would be nice if the "natural" ordering on A(f) had the property that
A(f) <= A(g) iff f is O(g)
Theta(g) is a set, and the most natural ordering on sets is subsetting/inclusion. However, Theta(x) is not a subset of Theta(x^2), even though x is O(x^2)! So the natural ordering on sets doesn't do what I want.
It might be possible to define an ordering on Theta-classes that does what I want, though.
Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use
O(f) <= O(g) for f is O(g)
O(f) = O(g) for f is Theta(g)
O(f) >= O(g) for f is Omega(g)
>Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use
> O(f) <= O(g) for f is O(g)
> O(f) = O(g) for f is Theta(g)
> O(f) >= O(g) for f is Omega(g)
>Is that true?
Yeah, I'm pretty sure that will work (haven't checked it very rigorously though). The definition of O(f) <= O(g) would simply be O(f) \subset O(g), which immediately satisfies almost all criteria (only tricky bit is proving that either O(f) is a subset of O(g) or the other way around).
For little o I think you should be able to use O(f) < O(g), using the ordering defined above.
I'm afraid the author is correct in using big-O here instead of Omega or little-o.
For comparison, suppose that someone claims that for all x, sin(x) ≤ 1/2. That would just be wrong. If someone claims that sin(x) ≤ 2, then that is true, but not as informative as saying that sin(x) ≤ 1. There's something special about 1 here. If you want to highlight that, you can say that 1 is the least upper bound for sin(x). This is a bit of a mouthful, but we cannot achieve the same meaning by just replacing "≤" by "≥" or "=" or "<". Any of these replacements would just make the statement incorrect.
Big-O is something like the asymptotic version of ≤. For example, how many comparisons does heapsort need to sort an array of length n? If someone says O(n), that's just wrong. If someone says O(n^2), then that's correct, but not as informative as saying O(n log n). O(n log n) is special here, since it is the smallest complexity class that contains the number of comparisons. Again, it is a bit of a mouthful, but we cannot say the same thing by just replacing big-O by Omega, Theta, or little-o (the asymptotic versions of ≥, =, and <, respectively). For example, Theta(n log n) and Omega(n log n) are incorrect, since heapsort only requires a linear number of comparisons if the array already happens to be sorted.
The author argues that random memory access time is O(sqrt(n)), meaning that for large n, it might take up to constant * sqrt(n) time, but might also be faster if the memory to be accessed happens to be very close. Using Omega(sqrt(n)) instead would mean that random memory access can take an arbitrarily long time, but at least constant * sqrt(n). This is not what the author is trying to say.
That page says o(f) == O(f) and not Theta(f). When you say "small-o is a claim that your process can't be faster than -this-", that seems to match the definition of Omega(f). Did you mean that the author should have used big-Omega?
As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)