3 ms·

Well, it's big-O of exponential!

• JoshTriplett 10y ago
  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).
  • JadeNB 10y ago
    I think that your parent was making precisely that point as a joke.
  • mjhoy 10y ago
    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.
    • smallnamespace 10y ago
      Why can't you use big theta to talk about average case?
      • mjhoy 10y ago
        You can, but strictly speaking you have to say, "big theta of the average case"!