18 flashcards · Shared on 19 August 2026 by AtomAI Library
Flip each card to check yourself.
What does a running time of O(f(n)) mean?
The running time is bounded above by a constant multiple of f(n) for sufficiently large n
What does a running time of O(f(n)) mean?
The running time is bounded above by a constant multiple of f(n) for sufficiently large n
What property makes a sorting algorithm stable?
It preserves the relative order of elements with equal keys
What is the worst-case lower bound for comparison-based sorting?
Ω(n log n)
Which complexity profile describes standard merge sort?
O(n log n) in the worst case and typically O(n) auxiliary space for arrays
Why does merge sort work well for large data sets stored externally?
It accesses data sequentially during merging
What are the average-case and worst-case time complexities of quicksort?
Average O(n log n), worst O(n²)
Which situation can cause quicksort to reach its O(n²) worst case?
Repeated pivot choices create highly unbalanced partitions
Which statement about heapsort is correct?
It has O(n log n) worst-case time and is usually not stable
How does insertion sort perform on an already sorted array when it stops scanning as soon as the insertion position is found?
O(n) time
Which description best matches selection sort?
It performs Θ(n²) comparisons in all cases and typically uses only O(n) swaps
What allows an optimized bubble sort to finish in O(n) time on an already sorted array?
Stopping after a pass makes no swaps
When is counting sort most appropriate?
When integer keys lie in a reasonably small known range
If n is the number of elements and k is the size of the key range, what is the time complexity of counting sort?
O(n + k)
Why must the sorting method used for each digit in standard radix sort be stable?
To preserve the ordering established by previously processed digits
Under common assumptions, what distribution allows bucket sort to achieve expected linear time?
Elements are distributed roughly uniformly among the buckets
What is an adaptive sorting algorithm?
An algorithm whose performance can improve when the input is partially sorted
Which algorithm is generally stable, in place, and well suited to small or nearly sorted inputs?
Insertion sort
What is the main reason non-comparison sorts can run faster than Ω(n log n)?
They exploit properties of keys, such as a bounded integer range or digit representation