Comment by OJFord
2 years ago
It's usually what people mean when they use O, really, colloquially anyway. Theta's like you actually identified the right 'magnitude curve'; what big-O actually says is much weaker, it's only an upper bound. You can say something's O(n) when actually it's constant, etc. But generally we don't, if someone says casually it's O(n) they mean 'and also Omega(n)', i.e. it's Theta(n).
(Or at least, it is when talking about something specific - how does this function behave, say. If you talk about needing something to happen linearly then that's a fine use of O - of course you're also happy with constant time if linear is ok.)
O is short for Omicron btw, lest you think it's O and then we suddenly went Greek for no apparent reason!
I was so confused by this when I learned it after first hearing about big-O notation. Like why are we only talking about the upper bound? Isn't the lower bound at least as, if not more, important? (spoiler: yes) I'm glad you wrote this since it reinforces that understanding.
> Isn't the lower bound at least as, if not more, important? (spoiler: yes)
I can't think of any situations where I care about the lower bound.
I mainly care about the upper bound and the average. Beyond that some percentile statistics are good.
And by "the" upper bound, I mean a tight upper bound for it to be useful. But you want a tight lower bound too, or it'll just be O(1) and that has no value at all.
And many algorithms have quick exit situations that give them a tiny lower bound and make big-theta invalid.
(Unless by "lower bound" you actually mean "lowest/tightest upper bound"?)
Yes what you're describing is theta - both an upper and lower bound (within constant factor).
Unless we're talking about 'we need to do this within O(...)', it is generally what we mean (as software engineers, not math/CS academics) even when we say O.
Because as you point out, it would be stupid to, say, file a bug report that some function is O(n^100) and too slow if it's also O(n^2) - both are correct (any time the latter is) but it's not really helpful to say the former. Theta effectively says you've found the smallest O.
2 replies →