Re:2017 Chevrolet Bolt EV
by herge on Monday October 31, 2016 @11:27AM
(#12837630)
Well, it's big-O of exponential!
[ Parent
| on HN ]
Re:2017 Chevrolet Bolt EV
by JoshTriplett on Monday October 31, 2016 @11:36AM
(#12837722)
People often use big-O (asymptotically bounded above) when they really want big-Θ (theta, asymptotically bounded above and below). Strictly by the definition, for instance, binary search is O(e^x), as well as O(x^12), O(x), and O(lg x). However, binary search is Θ(lg x), and not Θ(any of those other functions).
With big theta you strictly have to talk about best and worst cases, because for e.g. insertion sort, what's true of worst case is not true of best case (and vice versa). For big-O, what's true of worst case is also true of best case, so talking about worst case suffices. Big-O is less precise and therefore more useful, because average case usually = worst case anyway.
Re:2017 Chevrolet Bolt EV
by smallnamespace on Monday October 31, 2016 @12:32PM
(#12838378)
Why can't you use big theta to talk about average case?
You can, but strictly speaking you have to say, "big theta of the average case"!