An algorithm is a step-by-step method for solving a problem, and Big-O notation describes how the amount of work grows as the input size increases. This matters because two programs can both be correct but have very different speeds for large inputs. Instead of timing a program on one computer, Big-O focuses on the growth pattern of the number of steps.
It helps programmers and mathematicians compare efficiency in a general way.
Understanding Math: Algorithms and Big-O Notation
To analyse a method, choose the operation that is repeated most often. In a search, this may be comparing a target with one list item. In sorting, it may be comparing two items or moving one item.
Then count how that operation changes when the list becomes larger. A method can contain several stages.
If one stage takes a linear number of steps and another takes a quadratic number, the quadratic stage eventually dominates. This is why an inefficient part of a program can control the behaviour of the whole program, even if the rest is carefully written.
The structure of the instructions gives useful clues. Steps performed one after another usually add their costs. A loop inside another loop can multiply costs, but students should not assume that every nested loop is quadratic.
The inner loop may run fewer times on later passes, or it may stop early. Conditions matter too.
A search that finds an item near the start may finish quickly, while an unsuccessful search may inspect every item. Computer scientists often discuss worst case, average case, and best case separately because each describes a different situation a user might experience.
Growth rates become visible in familiar tasks. Looking through a pile of unsorted names is a linear search. Finding a word in an alphabetised paper list can use repeated halving, which is much faster for a huge list.
Sorting appears when a music app orders songs, a shop ranks products, or a school system organises marks. Route planners, spelling checkers, and game programs use many algorithms behind the screen.
A method that seems fast with twenty items may become unusable with millions. Exponential growth is especially important in problems that try every possible arrangement, such as testing possible schedules or routes.
Big-O is not a stopwatch. It does not tell the exact number of seconds on a particular phone or computer. Real speed depends on hardware, programming language, data storage, and the size of each item.
Memory use matters too. An algorithm may save time by storing extra information, while another uses less memory but repeats more work. When learning, practise tracing a small example by hand.
Write down how many times each loop runs and identify the largest growing part. Then test edge cases such as an empty list, one item, repeated values, or a target that is missing. These checks build the habit of connecting abstract growth rates to actual program behaviour.
Key Facts
- Big-O describes an upper bound on growth: f(n) = O(g(n)) means f(n) grows no faster than a constant multiple of g(n) for large n.
- Common growth rates from fastest to slowest are O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), and O(n!).
- Constant factors are ignored in Big-O, so 5n + 20 = O(n).
- Lower-order terms are ignored for large n, so n^2 + 100n + 7 = O(n^2).
- A loop that runs n times is usually O(n), while nested loops that each run n times are usually O(n^2).
- Binary search on a sorted list has runtime O(log n), while linear search has runtime O(n).
Vocabulary
- Algorithm
- An algorithm is a precise sequence of steps used to solve a problem or complete a task.
- Input size
- Input size is the amount of data an algorithm processes, often represented by n.
- Runtime
- Runtime is the number of steps or amount of time an algorithm needs to finish.
- Big-O notation
- Big-O notation describes how an algorithm's runtime or memory use grows as input size becomes large.
- Asymptotic growth
- Asymptotic growth is the long-term growth behavior of a function as n becomes very large.
Common Mistakes to Avoid
- Keeping constant factors in the final Big-O answer is wrong because Big-O focuses on growth rate, so O(3n) should be written as O(n).
- Keeping lower-order terms is wrong because they become less important for large inputs, so O(n^2 + n) should be simplified to O(n^2).
- Assuming every loop means O(n) is wrong because a loop can run a fixed number of times, n times, log n times, or depend on another variable.
- Comparing algorithms only using small input sizes is misleading because slower growth rates often become much better only when n is large.
Practice Questions
- 1 An algorithm takes 4n + 12 steps. What is its Big-O runtime, and how many steps does it take when n = 50?
- 2 An algorithm uses two nested loops, and each loop runs from 1 to n. How many total inner-loop operations occur when n = 100, and what is the Big-O runtime?
- 3 A sorted list contains 1,000,000 items. Explain why binary search is usually more efficient than linear search for finding one item.