What is the time complexity for quicksort, mergesort, and a hash-based lookup in Big-O terms?

What is the time complexity for quicksort, mergesort, and a hash-based lookup in Big-O terms?

• A. Quicksort O(n^2) average; Mergesort O(n log n); Hash-based lookup O(log n) average.
• B. Quicksort O(n log n) average; O(n^2) worst; Mergesort O(n log n); Hash-based lookup O(1) average; O(n) to build.
• C. Quicksort O(log n); Mergesort O(log n); Hash-based lookup O(1) average.
• D. Quicksort O(n); Mergesort O(n); Hash-based lookup O(n^2) average.

Answer: (B)

Quicksort’s time grows like n log n on average because each partition step splits the data roughly in half and you repeat this across about log n levels, with O(n) work at each level. If the pivot is consistently the smallest or largest element, you get a worst-case pattern that yields O(n^2). Mergesort also runs in n log n time consistently because it always divides the input in half and then merges the halves in linear time, across about log n levels, without depending on the input order. Hash-based lookup shines with average constant time search, O(1), thanks to indexing by a hash function. Building the table from n items takes O(n) on average. While collisions can affect performance in worst cases, the typical assumption is that lookups are constant time on average and building is linear. So the combination matches: quicksort averages to O(n log n) with a worst case of O(n^2); mergesort is O(n log n); and hash-based lookup is O(1) average for lookups with O(n) to build.

Quicksort’s time grows like n log n on average because each partition step splits the data roughly in half and you repeat this across about log n levels, with O(n) work at each level. If the pivot is consistently the smallest or largest element, you get a worst-case pattern that yields O(n^2).

Mergesort also runs in n log n time consistently because it always divides the input in half and then merges the halves in linear time, across about log n levels, without depending on the input order.

Hash-based lookup shines with average constant time search, O(1), thanks to indexing by a hash function. Building the table from n items takes O(n) on average. While collisions can affect performance in worst cases, the typical assumption is that lookups are constant time on average and building is linear.

So the combination matches: quicksort averages to O(n log n) with a worst case of O(n^2); mergesort is O(n log n); and hash-based lookup is O(1) average for lookups with O(n) to build.