Algorithms & Complexity
⏱ ~3-min readAceMark Guide
What this topic is really about
Dijkstra's shortest-path algorithm fails with negative edge weights.. Dijkstra's algorithm permanently finalises a node's shortest distance when it is removed from the frontier, which is only valid if no later negative edge can reduce that distance, so negative edge weights break it.
Merge sort guarantees a time complexity of O(n log n) in the worst case. Merge sort always divides the data into balanced halves regardless of input, so its worst case stays at O(n log n), whereas quicksort can degrade to O(n^2) with poor pivots.
See the mechanism
Each comparison cuts the remaining search interval in half, so after k steps the interval size is n/2^k. A diagram for this topic isn't available yet — the worked example below walks the same reasoning step by step.
An exam-style question, fully explained
What is the worst-case time complexity of binary search on a sorted array of n elements?
- Identify what the question tests: What is the worst-case time complexity of binary search on a sorted array of n elements.
- Binary search discards half of the remaining elements on each comparison, so the number of steps grows with the logarithm of n, giving O(log n).
- Linear O(n) is the complexity of a sequential scan, which does not exploit the array being sorted.
- Why it matters: Each comparison cuts the remaining search interval in half, so after k steps the interval size is n/2^k. Solving n/2^k ≤ 1 gives k = ⌈log₂ n⌉, which grows logarithmically with n. This is far faster than a linear scan (O(n)) that checks each element sequentially.
Traps the examiner sets
- Learners often mistake binary search for O(1) because it seems very fast, or they confuse it with sorting algorithms that are O(n log n).
- Many people mistakenly assume that the time complexity of bubble sort is always O(n^2), but this is only true for the average and worst cases. With the swap-detection optimisation, the best-case time complexity is actually O(n).
- Cycles and disconnected vertices do not affect Dijkstra's algorithm, but negative edge weights do.
- Some people mistakenly believe that merge sort uses less memory or is an in-place algorithm, but it typically requires extra O(n) space for merging. Others may think quicksort is always faster, but its average-case performance can be slower than merge sort's worst-case performance due to poor pivot choices.
- Depth-first search follows one branch as far as possible using a stack before backtracking.
Test your recall
Answer each from memory — you'll see instantly whether you're right and why.
Run a focused 10-question mini-mock on Algorithms & Complexity and see it stick.
Practice more of this topic →