title: How is the complexity of bucket sort is O(n+k) if we implement buckets using linked lists?
body: <p>I am curious about why bucket sort has a runtime of O(n + k) if we use buckets implemented with linked lists.  For example, suppose that we have this input:</p>
  
  <pre><code>n = no of element= 8
  k = range = 3
  
  array = 2,2,1,1,1,3,1,3
  </code></pre>
  
  <p>The buckets will look like this:</p>
  
  <pre><code>1: 1 -&gt; 1 -&gt; 1 -&gt; 1
  2: 2 -&gt; 2
  3: 3 -&gt; 3
  </code></pre>
  
  <p>The total time spent inserting into these buckets is O(n), assuming that we store a tail pointer in the linked lists.</p>
  
  <p>For deleting we have to go to each bucket and then delete each node in that bucket. Hence complexity should be O(K * average length of link list of bucket) as we are traversing each linked list.</p>
  
  <p>However, I read that bucket sort's complexity is O(n + k).  Why doesn't this agree with my analysis?  Please correct me as I am still learning computational complexity.</p>