title: Run-Times: Bounds vs Case
body: <p><strong>Note:</strong> Please do not tag this as homework! I am not a student and this is not an assignment. I am a software engineer dusting off my old Data Structures &amp; Algorithms textbook and trying to remember stuff I learned years ago and that I cannot seem to find anywhere online.</p>
  
  <p>I recall a specific lecture, and it is reinforced in my textbook, that algorithm bounds (upper, tight and lower) and cases (best, average and worst) are not one in the same. But for the life of me I can't remember how the two concepts are different.</p>
  
  <p>To me, if some algorithm is O(n) worst-case, then it can perform any worse than some linear function, such as <code>f(n) = cn + k</code>. Since we are guaranteed this in the worst case, it seems to me that its upper-bound is also linear.</p>
  
  <p>I know I'm wrong, I just can't figure out why.</p>
  
  <p>I'm a contextual learner, so if someone could provide a meaningful example where either worst-case is not upper bound, or best case is not lower bound, or where average case is not tight-bound, that would probably get through to me the fastest.</p>
  
  <p>Thanks for any clarity on this!</p>