Data Structures and Algorithms Flashcards
7 cards from real IKM practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Data Structures and Algorithms flashcards as text
What is the worst-case time complexity of quicksort when the first element is always chosen as the pivot and the input is already sorted?
Answer: O(n^2)
A sorted input with a first-element pivot creates maximally unbalanced partitions of size n-1 and 0, giving O(n^2).
Which of the following sorting algorithms is stable in its standard implementation?
Answer: Merge sort
Standard merge sort preserves the relative order of equal keys by taking from the left half first on ties.
What is the lower bound on the worst-case number of comparisons for any comparison-based sorting algorithm?
Answer: Ω(n log n)
A decision tree must have at least n! leaves, so its height is at least log2(n!) = Ω(n log n).
What is the time complexity of counting sort for n integers in the range 0 to k?
Answer: O(n + k)
Counting sort makes one pass over the n inputs and one pass over the k-sized count array.
What is the best-case time complexity of insertion sort?
Answer: O(n)
On an already sorted array, each element needs only one comparison, so the total work is linear.
How much auxiliary space does an in-place heap sort require?
Answer: O(1)
Heap sort rearranges elements within the input array using only a constant number of extra variables.
Which recurrence relation describes the running time of merge sort?
Answer: T(n) = 2T(n/2) + O(n)
Merge sort solves two half-size subproblems and merges them in linear time.