News for hackers. Stuff that matters.
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).
Re:2017 Chevrolet Bolt EV by mjhoy on Monday October 31, 2016 @12:03PM (#12838038)
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?
Re:2017 Chevrolet Bolt EV by mjhoy on Monday October 31, 2016 @12:36PM (#12838423)
You can, but strictly speaking you have to say, "big theta of the average case"!
Re:2017 Chevrolet Bolt EV by JadeNB on Monday October 31, 2016 @11:52AM (#12837907)
I think that your parent was making precisely that point as a joke.