iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
Big-O describes how an algorithm’s work or memory use grows as its input grows. It is a way to compare growth patterns—not a prediction of how many seconds a program will take. For example, a linear scan of a list may need to inspect each item, while binary search on a sorted list repeatedly cuts its search range in half.
What does Big-O mean in plain English?
Big-O notation summarizes how a resource used by an algorithm changes as the input gets larger. The resource might be the number of steps, or the amount of memory. The input size is usually written as n; for a list, n could mean the number of items.
| # | Preview | Product | Price | |
|---|---|---|---|---|
| 1 |
|
Introduction to Algorithms, fourth edition | $99.47 | Buy on Amazon |
| 2 |
|
Algorithms (4th Edition) | $68.77 | Buy on Amazon |
| 3 |
|
Introduction to Algorithms, 3rd Edition | $83.63 | Buy on Amazon |
| 4 |
|
Algorithms | $142.22 | Buy on Amazon |
| 5 |
|
Algorithm Design | $223.93 | Buy on Amazon |
Informally, saying an algorithm uses O(g(n)) work means that, once the input is sufficiently large, its work is bounded by a constant multiple of the growth pattern g(n). Carnegie Mellon’s course material puts the distinction succinctly: “Note that run time here refers to the number of algorithmic steps that the function takes rather than wall-clock time.” (Carnegie Mellon course material)
So O(n) says that work grows in proportion to input size, while O(n²) describes a pattern that grows roughly with the square of input size. Neither expression tells you the exact step count for a particular input or the elapsed time on a particular computer.
#1 Best Overall
- color: White
- INTRODUCTION TO ALGORITHMS, FOURTH EDITION
What does the O in Big-O formally say?
Big-O is an asymptotic upper bound. Formally, f(n) is in O(g(n)) if there are fixed positive constants c and n₀ such that, for every n ≥ n₀, f(n) ≤ c·g(n). Here, f(n) can represent an algorithm’s step count or another resource measure.
This definition allows a bound to be valid but unnecessarily loose. For instance, NIST notes that n² + 3n + 4 is O(n²), and 3n + 4 is also O(n²)—but the second bound says less than the tighter O(n) description would. In everyday algorithm analysis, people generally use the tightest useful bound they have established. Big-Theta, written Θ(g(n)), is the notation for a matching asymptotic upper and lower bound. (NIST Dictionary of Algorithms and Data Structures; Khan Academy on Big-Theta)
Rank #2
How to read common Big-O classes
The expressions below describe growth as n increases. Their order is useful for comparing how quickly work can scale, but it does not account for every implementation detail.
| Notation | Plain-language growth | Example or intuition |
|---|---|---|
| O(1) | Constant | Reading one array element by its index takes a fixed number of steps in the standard model. (Jay Wengrow, A Common-Sense Guide to Data Structures and Algorithms) |
| O(log n) | Logarithmic | Binary search repeatedly halves the remaining range in a sorted array. |
| O(n) | Linear | A scan may inspect every item in a list. |
| O(n log n) | Linearithmic | A common growth class in analyses of efficient sorting algorithms. |
| O(n²) | Quadratic | Comparing many pairs of items can produce work that grows with the square of the input size. |
These are broad growth patterns, not labels that can be proven just by glancing at a few lines of code. For example, nested loops often suggest quadratic work, but the loops’ ranges and behavior determine the actual analysis. OpenStax presents these classes as a way to compare growth rates, rather than as exact timing guarantees. (OpenStax, Introduction to Computer Science)
Rank #3
Why binary search is O(log n) and a scan is O(n)
Sequential scan: O(n) in the worst case
Suppose you look for a name in an unsorted list, starting at the first item. If the name is last—or absent—you may have to check every item. With n items, that worst-case step count grows proportionally to n, so the worst-case time complexity is O(n).
Binary search: O(log n) in the worst case
Binary search requires a sorted array. It checks a middle item, then discards the half of the remaining range that cannot contain the target. Each step roughly halves the candidates, so the number of steps grows logarithmically with n. Its worst-case time complexity is O(log n). (OpenStax, Introduction to Computer Science; University of Texas at Austin, Introduction to Algorithms)
Rank #4
If the input doubles, a full scan’s work roughly doubles. For binary search, doubling the input adds about one halving round. These are growth intuitions, not promises about exact elapsed time or every implementation.
Recommended Free Tools
Does Big-O mean worst-case runtime?
No. Big-O itself is an upper-bound notation; it does not specify which inputs or conditions are being analyzed. “Worst case” describes a particular way of measuring an algorithm’s behavior, and it should be stated separately. A complexity claim should make clear whether it describes best-case, average-case, worst-case, or another condition. When the intended claim is a tight growth rate, use the tightest bound supported by the analysis. (NIST Dictionary of Algorithms and Data Structures; Khan Academy on Big-Theta)
Best Value
How should you compare two algorithms?
Before deciding which algorithm is better, check that the comparison is measuring the same thing under the same conditions. Use this checklist:
- Resource: Are you comparing steps (time complexity), memory, or another resource?
- Input size: What does n count—records, characters, array items, or something else?
- Case: Is the bound for best, average, worst, or a specified input condition?
- Scale: How large are the inputs likely to become?
- Practical performance: Big-O omits constant factors and does not provide wall-clock time. For a small workload, it cannot by itself show which implementation will feel faster.
For a search task, binary search has a better asymptotic growth rate than a linear scan, but it assumes sorted data. Whether that is the relevant choice depends on the task and its conditions; the notation alone does not settle every practical trade-off. (Carnegie Mellon course material; OpenStax, Introduction to Computer Science)
Where to practice
For a guided introduction, Jay Wengrow’s A Common-Sense Guide to Data Structures and Algorithms, Second Edition, is a beginner-friendly algorithms book with a dedicated Big-O chapter and related exercises. It is a broader algorithms book, not a Big-O-only manual. (The Pragmatic Bookshelf)
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
