title: What is the worst case complexity for bucket sort?
body: <p>I just read the Wikipedia page about <a href="http://en.wikipedia.org/wiki/Bucket_sort" rel="nofollow">Bucket sort</a>. In this article they say that the worst case complexity is O(n²). But I thought the worst case complexity was O(n + k) where k are the number of buckets. This is how I calculate this complexity:</p>
  
  <ol>
  <li>Add the element to the bucket. Using a linked list this is O(1)</li>
  <li>Going through the list and put the elements in the correct bucket =  O(n)</li>
  <li>Merging the buckets = O(k)</li>
  <li>O(1) * O(n) + O(k) = O(n + k)</li>
  </ol>
  
  <p>Am I missing something? </p>