Quiz · Medium
Twenty questions on sorting algorithms, binary search, BFS and DFS, shortest paths, spanning trees, Huffman coding and dynamic programming.
Which complexity class does the curve that rises most steeply in this chart belong to?
O(n²)
O(n log n)
O(2ⁿ)
O(n)
Exponential growth quickly overtakes every polynomial curve. The orange curve is n², which grows fast but more slowly than 2ⁿ.
Which sorting algorithm is stable, always O(n log n), and needs O(n) extra space?
Merge sort
Quicksort
Heap sort
Selection sort
Merge sort splits in halves and merges with a temporary array. Quicksort and heap sort are not stable; selection sort is O(n²).
Merge sort splits [38, 27, 43, 3, 9, 82, 10] as shown. How many times is the array split before every piece has one element (the number of levels of splitting)?

2
4
7
3
7 → 4 and 3 → pieces of at most 2 → single elements: three levels of splitting, which is ceil(log₂ 7). Image: public domain, via Wikimedia Commons.
In quicksort with the last element as pivot, what input causes the worst case?
A random permutation
An already sorted array
An array of all different values in random order
An array with many duplicates only
On sorted input the last element is the maximum, so each partition removes just one element: n + (n − 1) + … = O(n²). A random permutation gives an expected O(n log n). With many duplicates a naive partition can also degrade, but sorted input is the classic case.
The picture shows binary search for 7 in a sorted array of 17 elements. How many elements are compared before 7 is found?

3
5
4
9
It compares with 14 (7 < 14), 6 (7 > 6), 8 (7 < 8) and finally 7: four comparisons. Linear search from the start would need five. Image: AlwaysAngry, CC BY-SA 4.0, via Wikimedia Commons.
What is the worst-case number of comparisons binary search needs on a sorted array of 1,000 elements?
10
1,000
500
100
ceil(log₂ 1000) = 10 since 2¹⁰ = 1024. Each step halves the search range.
Which algorithm finds the shortest path in an unweighted graph?
Depth-first search
Kruskal's algorithm
Topological sort
Breadth-first search
BFS explores vertices in order of distance from the source, so the first time it reaches a vertex is along a shortest path. DFS can reach a vertex by a long route first.
Dijkstra's algorithm is run from A on the graph. What is the shortest distance to E?
10
11
12
13
A→C (2) →B (3) →D (8) →E (11). The edge C–E gives 2 + 10 = 12, which is longer.
Why can't Dijkstra's algorithm be used on graphs with negative edge weights?
It runs out of memory
It only works on trees
A settled vertex may later have a shorter path
It cannot use a heap
Dijkstra finalizes the closest unsettled vertex, assuming nothing can make it closer. A negative edge breaks that assumption. Use Bellman-Ford instead.
Which algorithm builds a minimum spanning tree by sorting edges and rejecting those that form a cycle?
Kruskal's algorithm
Prim's algorithm
Dijkstra's algorithm
Bellman-Ford
Kruskal sorts edges by weight and uses union-find to skip cycle-forming edges. Prim grows a single tree from a start vertex.
A graph has 8 vertices and is connected. How many edges does a minimum spanning tree of it have?
8
9
28
7
A spanning tree has V − 1 edges: 7.
A DFS visits the vertices of this tree in the order shown by the numbers. Which of the following describes DFS?

It visits all neighbours of the start first
It explores as deep as possible, then backtracks
It always finds the shortest path
It uses a queue
DFS goes 1 → 2 → 3 → 4 → backtracks to 5, 6 … It uses a stack or recursion. Image: Alexander Drichel, CC BY-SA 3.0, via Wikimedia Commons.
What is the time complexity of building a Huffman code for n symbols using a min-heap?
O(n)
O(n²)
O(n log n)
O(2ⁿ)
There are n − 1 merges, each with O(log n) heap operations.
Which of these symbols gets the longest code in the Huffman tree shown?

'o' (frequency 1)
The space character (frequency 7)
'e' (frequency 4)
'f' (frequency 3)
Rare symbols end up deep in the tree: 'o' has a 5-bit code (00110), 'f' has 4 bits, while the space and 'e' have 3 bits each. Image: public domain, via Wikimedia Commons.
Which statement about comparison-based sorting is true?
Some algorithms sort in O(n) in the worst case
Quicksort is always O(n log n)
Merge sort needs O(1) space
Every comparison sort needs Ω(n log n) comparisons in the worst case
A decision tree for n elements has at least n! leaves, so its height is at least log₂(n!) = Θ(n log n). Counting sort is O(n + k) but is not comparison based.
Which technique solves the 0/1 knapsack problem correctly in O(nW) time?

Greedy by value
Dynamic programming
Greedy by value-to-weight ratio
Binary search
Greedy rules can fail for 0/1 knapsack. The DP table over items and capacities is correct and pseudo-polynomial. Image: VectorVoyager, CC BY-SA 4.0, via Wikimedia Commons.
True or false: Python's built-in sorted() is stable.
True
False
Timsort is stable, so elements with equal keys keep their original relative order.
What is the time complexity of naive recursive Fibonacci fib(n) = fib(n−1) + fib(n−2)?
O(n)
O(n log n)
Exponential, about O(1.618ⁿ)
O(n²)
The call tree roughly multiplies by φ ≈ 1.618 per level because of overlapping subproblems. Memoization reduces it to O(n).
True or false: insertion sort runs in O(n) time on an already sorted array.
True
False
Each element is compared once with its predecessor and never moved. That is why it is used for nearly sorted data.
Which sort should you choose to sort a million integers each between 0 and 999?
Counting sort
Bubble sort
Selection sort
Binary search
Counting sort runs in O(n + k) = O(10⁶ + 10³) and needs no comparisons. Bubble and selection sort are O(n²).