Big-O (or Ω or Θ) notation is orthogonal to notions of best-case or worst-case, which are merely constraints on the set of inputs we're considering. If, for exa

Big-O (or Ω or Θ) notation is orthogonal to notions of best-case or worst-case, which are merely constraints on the set of inputs we're considering. If, for example, you ask "what is the upper bound on best-case running time for linear search," then what you're actually asking is "given an input sequence that begins with the item being searched for, what is the upper bound on the running time." I think part of the confusion stems from the fact that when people supply bounds on best- or worst-case running times for deterministic algorithms, they often use Big-O notation when they're actually giving an asymptotically tight bound. So in the case of linear search's best case, O(1) is an upper bound, but the lower bound is of the same order, i.e. Ω(1). It's not incorrect, but it can be misleading. In the case of Quicksort, I think the answer to your question is yeah, pretty much. I mean, cases where you're dealing with nearly-sorted input are common in some domains and in that case you should be very much aware of the worst-case behavior of Quicksort, but otherwise I think the discussion from CLRS puts things in perspective: even if you had the bad luck of only ever receiving input sequences such that every partitioning led to a 99-to-1 split, then your running time is still going to be O(n lg n), since your recursion tree is going to be at most log-base-100/99(n) levels tall, which is the same as lg n / (lg 100/99), the denominator there being a constant factor that disappears in an asymptotic context.