AlgorithmsCollege3 topic explainers

Algorithms course

Designing and analyzing algorithms.

Topics in this course

1.Big-O Notation
Big-O notation describes how an algorithm's running time or memory grows as the input size $n$ grows, ignoring constant factors and lower-order terms. An algorithm that takes $3n^2 + 5n + 2$ steps is $O(n^2)$ , because for large $n$ the $n^2$ term dominates everything else.
- Drop constants and lower-order terms: $5n + 100$ is $O(n)$ .
- Sequential steps add; nested loops multiply.
- Halving the problem each step gives $O(\log n)$ .
Quick check: About how many halvings take 1024 items down to 1?
$10$
Includes a worked example, 3 common mistakes and 3 practice questions with answers. Study big-o notation
2.Searching and Sorting
Searching finds an item in a collection. Linear search checks each element in turn and works on any list in $O(n)$ time. Binary search works only on sorted data: it checks the middle element and discards half the list each step, finding any item among a million in about 20 comparisons.
- Binary search needs a sorted list and takes at most $\lceil \log_2(n + 1) \rceil$ comparisons.
- Insertion sort is fast on nearly sorted data.
- Merge sort is always $O(n \log n)$ but uses extra memory.
Quick check: Worst-case comparisons for binary search on 1000 sorted items.
$10$
Includes a worked example, 3 common mistakes and 3 practice questions with answers. Study searching and sorting
3.Recursion
A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case that is answered directly and a recursive case that moves toward it. Factorial is the classic example: $n! = n \times (n - 1)!$ , with $0! = 1$ as the base case.
- Always define the base case first and make sure every call moves toward it.
- Trace with a call tree to see the order of calls and returns.
- Recurrences describe cost: $T(n) = T(n - 1) + O(1)$ gives $O(n)$ ; $T(n) = 2T(n/2) + O(n)$ gives $O(n \log n)$ .
Quick check: Compute $5!$ recursively.
$120$
Includes a worked example, 3 common mistakes and 3 practice questions with answers. Study recursion

Topics in this course

1.Big-O Notation

2.Searching and Sorting

3.Recursion

Where to go next