Data Structures & Algorithms - Exam
and Interview Guide
Big-O, arrays, linked lists, trees, graphs, sorting and dynamic programming -
with worked examples
Complete Study Guide | Key Concepts | Examples | Practice Questions
, 1. Big-O Notation and Complexity Analysis
Big-O describes how runtime or memory grows as input size n grows. It captures the worst case and drops
constants and lower-order terms.
Notation Name Example
O(1) Constant Array index access
O(log n) Logarithmic Binary search
O(n) Linear Single loop
O(n log n) Linearithmic Merge sort
O(n^2) Quadratic Nested loops / bubble sort
O(2^n) Exponential Naive recursion (Fibonacci)
- Always analyse worst-case time AND space complexity.
- A hash map lookup is O(1) on average - the key trick behind many optimal solutions.
- Sorting first (O(n log n)) often unlocks a linear second pass.
- Recursion space = O(depth of call stack); watch for stack overflow.
TIP: When stuck in an interview, first state the brute force and its complexity, then optimise.
Interviewers reward the reasoning.
Page 1
and Interview Guide
Big-O, arrays, linked lists, trees, graphs, sorting and dynamic programming -
with worked examples
Complete Study Guide | Key Concepts | Examples | Practice Questions
, 1. Big-O Notation and Complexity Analysis
Big-O describes how runtime or memory grows as input size n grows. It captures the worst case and drops
constants and lower-order terms.
Notation Name Example
O(1) Constant Array index access
O(log n) Logarithmic Binary search
O(n) Linear Single loop
O(n log n) Linearithmic Merge sort
O(n^2) Quadratic Nested loops / bubble sort
O(2^n) Exponential Naive recursion (Fibonacci)
- Always analyse worst-case time AND space complexity.
- A hash map lookup is O(1) on average - the key trick behind many optimal solutions.
- Sorting first (O(n log n)) often unlocks a linear second pass.
- Recursion space = O(depth of call stack); watch for stack overflow.
TIP: When stuck in an interview, first state the brute force and its complexity, then optimise.
Interviewers reward the reasoning.
Page 1
