60 practice questions
Explain how binary search works and state the precondition.
mediumWhat is a linear search and when is it appropriate?
easyTrace binary search for target=7 in [1,3,5,7,9,11]. State mid index each step.
mediumCompare the number of comparisons needed by linear and binary search on a sorted list of 1024 items (worst case).
mediumTrace a linear search for the value 7 in the list [3, 9, 7, 2, 5]. How many comparisons are made before it is found?
easyExplain why binary search cannot be used directly on a linked list in the same efficient way as on an array.
hardWhat precondition must be satisfied before binary search can be used on a list?
easyTrace a linear search for the value 99 in the list [3, 9, 7, 2, 5], where 99 is not present. How many comparisons are made, and what does this represent?
mediumA program needs to check whether a single value exists in a small, unsorted list of 6 items, and this check will only be performed once. Which search algorithm is more appropriate?
easyExplain why binary search has a time complexity of O(log n).
mediumHow does insertion sort work?
mediumTrace bubble sort on [5,3,8,1]. Show list after each pass.
mediumDescribe the divide-and-conquer approach in merge sort.
mediumWhat is meant by a "stable" sorting algorithm?
mediumDescribe how insertion sort works, using the list [4, 2, 3] as an example of the first pass.
mediumA sorting algorithm is described as "stable". What does this mean?
hardMerge sort is used to sort the list [8, 4, 5, 2]. Show how the list is divided, and then how it is merged back together in sorted order.
mediumWhich sorting algorithm has a best-case time complexity of O(n), which occurs when the input list is already sorted?
mediumExplain how a bubble sort algorithm can be optimised to stop early if the list becomes sorted before all passes are complete.
mediumIn the worst case, how many passes does a standard bubble sort make to fully sort a list of n items?
mediumWorst-case complexity of quicksort and when does it occur?
hardHow does pivot choice affect quicksort performance?
hardDescribe the steps of the quicksort algorithm.
mediumWhat is the average-case time complexity of quicksort?
mediumQuicksort is applied to the list [5, 1, 4, 2, 8], using the last element (8) as the pivot. Show the result of the partition step.
hardWhy might a quicksort implementation choose its pivot value randomly, rather than always using the first or last element?
mediumExplain the base case of the recursive quicksort algorithm, and why it is necessary.
mediumWhich statement comparing quicksort and merge sort is correct?
hardExplain what is meant by 'in-place' partitioning in quicksort.
mediumA quicksort implementation always chooses the first element of the (sub-)list as the pivot. What is the time complexity when this is applied to a list that is already fully sorted in ascending order?
hardState worst-case time complexities of bubble sort, merge sort, and binary search.
mediumWhat makes an algorithm efficient?
easyWhat is space complexity?
mediumWhat is the Big O notation for an algorithm that checks all pairs in a list?
mediumWhat does O(1) mean for an algorithm's time complexity?
easyWhich of the following correctly orders these algorithms from most to least efficient for large n: O(n), O(n²), O(log n), O(1)?
mediumExplain why an algorithm's best-case time complexity is often less useful in practice than its average-case or worst-case complexity.
mediumExplain the difference between an algorithm with time complexity O(n) and one with time complexity O(n log n), giving an example of each.
mediumFor very large values of n, which time complexity represents the algorithm that takes the LONGEST to run?
easyExplain how counting the number of nested loops in an algorithm can help estimate its time complexity.
mediumWhat is an optimisation problem and give one example?
mediumA graph has nodes representing tasks and edges representing dependencies (task A must happen before task B). Which algorithm/technique could determine a valid order to perform all tasks?
hardExplain what it means for a problem to be described as 'tractable'.
mediumWhich of the following best describes an 'intractable' problem?
mediumExplain what is meant by the complexity classes P and NP.
hardThe Travelling Salesman Problem (finding the shortest route visiting a set of cities exactly once and returning to the start) is generally considered to be:
mediumExplain why an algorithm with exponential time complexity (e.g. O(2^n)) becomes impractical even for moderately sized inputs.
mediumWhich of the following is typically given as an example of an intractable problem?
mediumExplain what is meant by a problem being 'NP-complete'.
hardWhich of the following time complexities would generally be classed as 'polynomial time' (and therefore associated with tractable problems)?
easyWhat is the difference between a greedy algorithm and dynamic programming?
hardExplain Dijkstra's shortest path algorithm.
hardHow does a pre-order depth-first search traverse a tree?
hardWhat is a spanning tree of a graph and what does "minimum" mean?
hardIn Dijkstra's algorithm, why is the node with the smallest tentative distance always chosen next?
hardExplain the difference between a depth-first and breadth-first traversal of a tree, and the data structure typically associated with each.
mediumWhich algorithm would be most appropriate for finding the minimum spanning tree of a weighted, connected graph?
mediumExplain what is meant by a 'heuristic' approach to solving a problem, and when such an approach might be used.
mediumWhich of the following is an example of a heuristic approach to the Travelling Salesman Problem?
mediumDiscuss the trade-off between using a heuristic algorithm and an exact algorithm for a large, intractable problem.
medium| Big-O | Name | n=10 → n=1000 work grows… | Example |
|---|---|---|---|
| O(1) | Constant | no change | Array index; hash lookup (avg) |
| O(log n) | Logarithmic | barely (≈ 3 → 10) | Binary search |
| O(n) | Linear | ×100 | Linear search |
| O(n log n) | Linearithmic | ×~200 | Merge sort, quicksort (avg) |
| O(n²) | Quadratic | ×10,000 | Bubble / insertion sort |
| O(2ⁿ) | Exponential | astronomically | Naive recursive Fibonacci |
Suppose 1 operation = 1 microsecond, n = 1,000,000: O(n) ≈ 1 second O(n log n) ≈ 20 seconds O(n²) ≈ 11.5 DAYS O(2ⁿ) ≈ longer than the age of the universe This is why an efficient algorithm matters far more than a faster computer for large inputs.
P: problems solvable in polynomial time. NP: problems where a proposed solution can be VERIFIED in polynomial time. NP-complete problems are the hardest in NP — if any one had a polynomial-time solution, all of NP would (the famous open question, P = NP?). Problems with no known efficient solution are intractable; in practice we attack them with heuristics and approximation algorithms.
| Algorithm | Best | Avg / Worst | Space | Notes |
|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(1) | Works on any list, sorted or not |
| Binary search | O(1) | O(log n) | O(1) | Sorted list only; halves each step |
| Bubble sort | O(n) | O(n²) | O(1) | Simple; in place; slow on large lists |
| Insertion sort | O(n) | O(n²) | O(1) | Efficient on nearly-sorted data |
| Merge sort | O(n log n) | O(n log n) | O(n) | Divide & conquer; stable; needs extra space |
| Quicksort | O(n log n) | O(n²) worst | O(log n) | Fast in practice; in place; pivot choice matters |
low=0 high=6 mid=3 → list[3]=7 FOUND (1 comparison) find 11: low=0 high=6 mid=3 → 7 < 11 → search right, low=4 low=4 high=6 mid=5 → list[5]=11 FOUND (2 comparisons) find 8 (absent): low=0 high=6 mid=3 → 7<8 → low=4 low=4 high=6 mid=5 → 11>8 → high=4 low=4 high=4 mid=4 → 9>8 → high=3 low>high → NOT FOUND
5 vs 3 → swap → [3,5,8,1] 5 vs 8 → no swap → [3,5,8,1] 8 vs 1 → swap → [3,5,1,8] ← 8 now in final place Pass 2: [3,5,1,8] → [3,1,5,8] → 5 placed Pass 3: [3,1,5,8] → [1,3,5,8] Pass 4: no swaps → SORTED (early exit optimisation)
SPLIT: [4,2,7,1] → [4,2] [7,1] → [4][2] [7][1]
MERGE: [4]+[2] = [2,4] [7]+[1] = [1,7]
[2,4] + [1,7] → compare fronts: 1,2,4,7
= [1,2,4,7] ✓Finds the shortest path from a start node to all others in a weighted graph with non-negative edge weights. It keeps a tentative shortest distance to every node (start = 0, others = ∞), repeatedly selects the unvisited node with the smallest tentative distance, marks it visited (its distance is now final), and relaxes its neighbours (updates a neighbour's distance if going via this node is shorter). It explores outward in all directions like a flood.
Graph: A-B=4, A-C=1, C-B=2, C-D=5, B-D=1 Init: A=0, B=∞, C=∞, D=∞ Visit A: B=4, C=1 Visit C (smallest=1): B=min(4,1+2)=3, D=1+5=6 Visit B (3): D=min(6,3+1)=4 Visit D (4): done Shortest A→D = 4 (A→C→B→D)
Extends Dijkstra by adding a heuristic h(n) that estimates the cost from node n to the goal. Nodes are prioritised by f(n) = g(n) + h(n), where g(n) is the actual cost from the start so far. By steering exploration toward the goal, A* usually finds the shortest path while examining far fewer nodes than Dijkstra.
| Feature | Dijkstra's | A* |
|---|---|---|
| Priority | g(n) — cost from start | f(n) = g(n) + h(n) |
| Heuristic | None | Required (admissible for optimality) |
| Nodes explored | More — all directions | Fewer — guided toward the goal |
| Needs domain knowledge? | No | Yes — to design a good heuristic |
| Use case | Any non-negative weighted graph | Maps, games — where a heuristic exists |