Algorithms & complexity: practice questions with explanations

1What complexity measures

An algorithm is a finite list of precise steps that solves a problem, such as sorting a list or finding a name in a phone book.

Two algorithms can solve the same problem but take very different amounts of time. Complexity describes how the work grows when the input gets bigger.

The size of the input is called n: the number of items to sort, the length of a list, the number of nodes in a graph.

Think of looking for a name in a phone book of 1000 pages. Reading every page takes up to 1000 steps. Opening it in the middle and halving each time takes about 10 steps.

Time complexity counts the steps. Space complexity counts the extra memory. Both are written as a function of n.

Usually you look at the worst case: the most work over all inputs of size n. Sometimes the average case or the best case is asked instead.

2Big O and the growth classes

Big O notation keeps only what matters for large n. You drop constant factors and keep only the fastest-growing term.

For n = 1000 the n² term is 3 000 000, while 5n is only 5000. The smaller terms hardly change the total.

These classes appear again and again, from slowest to fastest growth:

• O(1), constant: reading an array element by its index.
• O(log n), logarithmic: binary search, which halves the problem each step.
• O(n), linear: one pass over all items, such as finding the largest value.
• O(n log n): good sorting algorithms such as merge sort.
• O(n²), quadratic: two nested loops over the items, such as bubble sort.
• O(2ⁿ), exponential: trying every subset. It becomes unusable quickly.

Big O is an upper bound: the work grows at most this fast. Ω (Big Omega) is a lower bound, and Θ (Theta) is a tight bound, both upper and lower.

The base of a logarithm does not matter in Big O, because logarithms with different bases differ only by a constant factor.

3Searching, sorting and recursion

A few algorithms come up in almost every course. Learn their complexities as facts.

• Linear search checks items one by one: O(n). Binary search needs a sorted array and halves the range each step: O(log n).
• Bubble, insertion and selection sort compare and swap items in nested loops: O(n²). Insertion sort is O(n) on an array that is already sorted.
• Merge sort splits the array in halves, sorts them and merges them: O(n log n) in every case, with O(n) extra memory.
• Quicksort splits around a pivot: O(n log n) on average, but O(n²) in the worst case, for example a sorted array with the first element as pivot.
• No sort that only compares items can beat Ω(n log n) in the worst case. Counting sort is faster because it does not compare.

A recursive function calls itself on a smaller input until it reaches a base case that it answers directly. Its running time is written as a recurrence:

• T(n) = T(n/2) + O(1) gives O(log n), like binary search.
• T(n) = 2T(n/2) + O(n) gives O(n log n), like merge sort.
• T(n) = T(n − 1) + O(n) gives O(n²).
• T(n) = 2T(n − 1) + O(1) gives O(2ⁿ).

Three design ideas are worth knowing. Divide and conquer splits, solves and combines. Greedy takes the locally best choice each step. Dynamic programming stores the answers to overlapping subproblems so they are computed once.

4The method step by step

To find the time complexity of a piece of code:

1. Decide what n is: the size of the input.
2. Count how many times each loop runs. A loop that adds 1 each time runs about n times. A loop that doubles or halves runs about log₂ n times.
3. Loops inside each other multiply. Loops one after the other add.
4. For a recursive function, write the recurrence: how many calls, on what size, plus the work per call.
5. Keep the fastest-growing term and drop the constants.
6. Check with a small number, for example n = 8 or n = 1024.

For a theory question, first name the algorithm or idea it describes, then recall its complexity and its conditions (sorted input, non-negative weights, overlapping subproblems).

5A worked example

Follow every step. Try to predict the next one before you open it.

6Common mistakes

• Multiplying loops that run one after the other. n + n = 2n is still O(n).
• Keeping constants, as in O(2n) or O(n/2). Both are O(n).
• Counting a doubling loop as n rounds. It runs about log₂ n times.
• Using binary search on unsorted data, or on a linked list where the middle cannot be reached in one step.
• Giving the average case of quicksort when the worst case is asked.
• Thinking Big O means “exactly”. O(n²) is an upper bound; Θ(n²) is the exact growth.

7How exam questions look

• Easy: key terms and facts. The complexity of binary search, merge sort or array access, the meaning of O, Ω and Θ, what recursion is.
• Medium: applying the concepts. The complexity of a code fragment, a recurrence to solve, how the time changes when n doubles, which algorithm fits a task.
• Hard: cases and analysis. The master theorem, worst cases of quicksort, greedy versus dynamic programming, and the classes P, NP and NP-complete.

P contains problems that can be solved in polynomial time. NP contains problems whose solutions can be checked in polynomial time. Every problem in P is in NP; whether P = NP is still unknown.