Exam II Flashcards
What is the time complexity of binary search?
O(log n) — it repeatedly halves the search space.
Why must data be sorted for binary search?
Binary search relies on comparing the target to the middle item and eliminating half the search space; this only works with sorted data.
What is the main idea of selection sort?
Repeatedly find the smallest element and swap it with the current index.
Time complexity of selection sort?
O(n²) — regardless of input order.
What is the best-case time complexity of insertion sort?
O(n) — when the array is already sorted.
Why is insertion sort efficient on nearly sorted arrays?
Fewer shifts are needed since elements are already close to their final positions.
What makes shell sort faster than insertion sort?
It sorts distant elements first, reducing the number of final swaps needed in later passes.
Worst-case time complexity of shell sort (with good gaps)?
O(n^1.5)
Merge sort time and space complexity?
Time: O(n log n), Space: O(n)
what type of algorithm is merge sort?
divide and conquer
Best and average case complexity of quicksort?
O(n log n)
what makes quicksort fast in practice?
in-place sorting and efficient partitioning
What is radix sort’s time complexity?
O(n * d) — d = number of digits.
when is radix sort most efficient?
When the number of digits (d) is small compared to n.
how does a queue differ from a stack?
Queue = FIFO, Stack = LIFO.
What’s the benefit of using a circular array for a queue?
Avoids unnecessary resizing by reusing space.
what does a deque support that a queue does not?
Insertion and removal from both front and back.
How are priority queues different from regular queues?
Items are dequeued based on priority, not insertion order.
Which implementation can insert in O(log n)?
Array-based with binary search + shift.
What is the time complexity of brute-force string matching?
O(n * m)
What does Boyer-Moore improve?
Skips ahead using bad character and good suffix rules → O(n/m) avg.
What is a rolling hash useful for?
Efficient substring hash updates (used in Rabin-Karp).
What is the key advantage of hashing?
Near constant-time lookups (O(1)).
What’s a collision in a hash table?
Two keys hash to the same index.
