English
Menu

Data Structures and Algorithms

Which is a typical case in which quicksort takes O(n²) time?

  1. AThe data is in random order and the pivot is chosen at random
  2. BThe number of data items is a power of two
  3. CThe data is already sorted and the first element is always used as the pivot
Show answer and explanation

Answer: C. The data is already sorted and the first element is always used as the pivot

Quicksort splits the elements into those smaller and those larger than the pivot, then splits each part again. If the data is already sorted and the first element is always the pivot, the pivot is the minimum every time and each split is lopsided, with zero elements on one side and all the rest on the other, so it makes n(n−1)/2 comparisons (4,950 for n = 100). Choosing the pivot at random or as the median of three values makes a long run of lopsided splits extremely unlikely. The number of items has nothing to do with this.

  • A. With a random pivot, lopsided splits are extremely unlikely to keep happening, and it averages O(n log n).
  • B. Whether the count is a power of two has nothing to do with lopsided splits.
  • C. Correct. The pivot is the minimum every time, so the splits are extremely lopsided.
Practice this topic Back to topic

Related calculators

Sorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write countsDijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. In merge sort, the two sorted runs 1, 4, 7, 9 and 2, 3, 8, 10 are merged into one by repeatedly comparing their front elements and outputting the smaller. When one run is empty, the rest of the other is output without comparisons. How many comparisons are made?
  2. A binary heap is stored in an array a[0], a[1], a[2], … with the root at a[0], filling each level from left to right starting at the top. Which are the children and the parent of a[4]?
  3. A max-heap, in which each parent's value is at least as large as its children's, is stored in an array with the root at a[0]. 45 is added to the heap 50, 30, 40, 10, 20, 35 by placing it at the end and then swapping it with its parent as long as it is larger than the parent. What is the resulting array?
  4. When a binary search tree is traversed in in-order (visiting the left subtree, then the node, then the right subtree), how are the values of the visited nodes ordered? Assume all values are distinct.
  5. The values 50, 30, 70, 20, 40, 60, 80 are inserted in this order into an empty binary search tree. In what order are the nodes visited when the tree is traversed in post-order (left subtree, right subtree, then the node)?