Foundations
Big-O Notation (Upper Bound)
Difficulty: Beginner
How do you compare two solutions to the same problem without ever running them on real hardware? Big-O is the symbolic shorthand that the entire industry uses to do exactly that, and it is the single most referenced notation in textbooks,...
Big-O Notation (Upper Bound)
How do you compare two solutions to the same problem without ever running them on real hardware? Big-O is the symbolic shorthand that the entire industry uses to do exactly that, and it is the single most referenced notation in textbooks, technical interviews, and engineering documentation.
Big-O Notation (Upper Bound) turns the growth-rate ideas you have been thinking about into precise notation. You will see what O(f(n)) formally means as an upper bound, walk through the seven complexity classes you will meet again and again (O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!)), and learn the rules for reading Big-O straight from code: single loops, nested loops, sequential blocks, conditional branches, and inputs with multiple variables like O(n + m) and O(n * m). You will also meet best, worst, and average case analysis so you know which scenario a Big-O statement is describing.
In Asymptotic Analysis Fundamentals, you saw why we count operations as a function of input size n, why constants and lower-order terms drop away, and how growth rates rank from constant to exponential. Big-O is the formal language for everything you reasoned about there: each growth-rate intuition becomes a concrete O(...) expression.
Once you can classify code by sight, you will be ready for Time Complexity Analysis Techniques, where you will apply these rules to longer, more realistic snippets and develop a systematic analysis workflow.
Prerequisites:
Asymptotic Analysis FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
State the formal intuition behind Big-O as an upper bound on growth rate.
Recognize and order the common complexity classes: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!).
Determine the Big-O of simple code snippets involving loops and conditionals.
Explain best case, worst case, and average case analysis.
Handle multiple input variables in Big-O expressions.
Why This Matters
01
Big-O is the most commonly used notation in industry, interviews, and documentation.
02
Every data structure and algorithm is described by its Big-O time and space complexity.
03
Interviewers expect you to state and justify Big-O on the spot for any code you write.
Key Terms
8 terms you'll encounter in this lesson
Big-O notation
A mathematical notation that describes an upper bound on the growth rate of an algorithm's resource usage as input size increases.
O(1) -- Constant
The algorithm's work does not change regardless of input size. Example: accessing an array element by index.
O(log n) -- Logarithmic
The work grows by a fixed amount each time the input doubles. Example: binary search.
O(n) -- Linear
The work grows proportionally to input size. Example: scanning every element of an array.
O(n log n) -- Linearithmic
Slightly worse than linear. Example: efficient sorting algorithms like merge sort.
O(n^2) -- Quadratic
The work grows as the square of input size. Example: checking all pairs of elements.
O(2^n) -- Exponential
The work doubles with each additional input element. Example: generating all subsets.
Worst case
The input that causes the algorithm to perform the maximum number of operations.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Big-O tells you the exact number of operations"
Big-O describes the growth rate, not the exact count. O(n) means the work grows linearly -- it could be n, 5n, or 100n operations.
"O(n) is always faster than O(n^2)"
For large n, yes. But for very small n, an O(n^2) algorithm with tiny constants might be faster in practice. Big-O is about scalability, not small-input speed.
"Big-O always describes the worst case"
Big-O is a notation for upper bounds, but you can apply it to best, worst, or average case. When someone says 'the Big-O is O(n)', they usually mean worst case, but it is good practice to specify.
"O(2n) is different from O(n)"
Constants are dropped in Big-O. O(2n) = O(n). Both describe linear growth.