Suppose a hash table uses buckets with sorted chaining. To insert a key, you need to search its bucket to verify that it is not present. If the table uses B buckets and contains N items, that takes...

Suppose a hash table uses buckets with sorted chaining. To insert a key, you need to search its bucket to verify that it is not present. If the table uses B buckets and contains N items, that takes roughly O(N B/ /2) steps on average. After you verify that the key is not present, you need to insert it in the correct position in its chain, which takes another O(N B/ /2) steps. Why is this faster than the O(N B/ ) steps needed to insert an item if the chains are not sorted?