The {best|average|worst} case time complexity of Binsort is:

\Theta(n + \mathrm{MaxKeyValue})
  • \Theta(n)
  • \Theta(n^2)
  • \Theta(n \log n)
  • \Theta(\mathrm{MaxKeyValue})

We need a separate bin for every key value.

And we need to look at every such bin.

So the cost has to be related to both the number of records and the number of bins.