IB Computer Science Topic B2.4.1: Efficiency of Specific Algorithms and Big O Notation Notes

Big O Notation: Describing How Cost Grows With Input Size

1. Big O notation describes how the cost of an algorithm grows as the input gets larger.
2. Time complexity measures how the number of operations changes with the size of the input.
3. Space complexity measures how much extra memory the algorithm needs as the size of the input changes.
4. Big O ignores the hardware and the language, so it compares the algorithms themselves rather than the machines they run on.

Complexity Classes: From Constant to Factorial

1. O(1), constant time
   1. The cost stays the same however large the input is, such as reading arr[7] from an array.
2. O(log n), logarithmic time
   1. Each step discards a fixed fraction of the data, such as binary search halving the range it still has to check.
3. O(n), linear time
   1. Cost rises in step with the input, such as one pass through an array to find the largest value.
4. O(n log n), log-linear time
   1. The pattern of the efficient sorts, quicksort and mergesort.
5. O(n²), quadratic time
   1. Usually a loop inside a loop over the same data, such as bubble sort and selection sort.
6. O(2ⁿ), exponential time
   1. Cost doubles with every extra element, such as the naive recursive Fibonacci algorithm.
7. O(n!), factorial time
   1. Cost grows factorially, such as generating every permutation in a brute-force travelling salesperson search.
8. The table below is the reason the class matters: the same algorithm that is instant on ten items can be unusable on a thousand.

Calculating Big O: Find the Dominant Term

1. Identify the basic operation that repeats, usually a comparison, a swap or an assignment inside a loop.
2. Count how the loops nest.
   1. A single loop over n items is O(n).
   2. A loop inside a loop, each running over n items, multiplies to O(n²).
   3. A loop that halves the remaining data each pass is O(log n).
3. Analyse recursion by depth and branching.
   1. A recursive call that reduces the problem by one each time, such as factorial, makes n calls and is O(n).
   2. A recursive call that makes two further calls each time, such as naive Fibonacci, is O(2ⁿ).
4. Drop constants and lower-order terms because only the fastest-growing term matters as n rises.
   1. O(2n + 3) simplifies to O(n).
   2. O(n² + n) simplifies to O(n²).

Space Complexity: The Memory the Algorithm Adds

1. Space complexity counts the extra memory an algorithm needs, not the memory already taken by the input.
2. O(1) space means the extra memory does not grow with the input.
   1. An in-place sort that holds one temporary variable while swapping is O(1), however long the array is.
3. O(n) space means the extra memory grows in step with the input.
   1. Copying the array into a second list, or building a call stack n frames deep in a recursive algorithm, is O(n).
4. Time and space pull against each other, so an algorithm can be made faster by storing more, or leaner by recomputing.

Choosing an Algorithm: Match the Complexity to the Constraint

1. Small or nearly sorted data: bubble sort and selection sort are simple to write and their quadratic cost barely shows.
2. Large data sets: an O(n log n) sort such as quicksort or mergesort repays the extra complexity many times over.
3. Sorted or indexed data: binary search finds an item in O(log n) instead of O(n).
4. Unsorted data searched once: linear search wins, because sorting first costs more than the single scan saves.
5. Tight memory: prefer an in-place O(1) space algorithm even where its time complexity is worse.
6. The four algorithms on this syllabus compare as follows.

These four algorithms are constructed and traced in B2.4.2 and B2.4.3; this page covers only how their cost is measured and compared.