Course contentsShow
← Computer Science
Lesson 280 of 2,8727. Introduction to Complexity AnalysisFree lesson

What is Big-O Notation?

Introduction to Big-O as a mathematical tool for describing algorithm growth rates and upper bounds on runtime.

What is Big-O Notation?

You'll learn: How Big-O notation provides a standardized mathematical way to describe how an algorithm's runtime grows as input size increases.

The Core Idea

Remember how we've been analyzing runtime by counting operations and identifying growth rates? We discovered that dominant terms matter most and constant factors get dropped when input size grows large. Big-O notation formalizes this intuition into precise mathematical language.

Big-O describes the upper bound of an algorithm's growth rate—essentially the worst-case scenario for how slowly it could run. It answers: "As input size n approaches infinity, how does the runtime scale?"

Mathematical Tool for Comparison

Big-O uses the letter O followed by a function in parentheses. For example:

  • O(1) means constant time—runtime doesn't grow with input size
  • O(n) means linear time—runtime grows proportionally with input size
  • O(n²) means quadratic time—runtime grows with the square of input size

When we write "this algorithm is O(n²)," we're saying: "In the worst case, this algorithm's runtime won't grow faster than some constant times n²."

Why Upper Bounds Matter

Big-O focuses on upper bounds because we need guarantees. We want to know: "What's the slowest this could possibly run?" This helps us make safe decisions about whether an algorithm will perform acceptably for our needs.

Think of it like a speed limit sign: it tells you the maximum speed allowed, giving you a boundary you can rely on when planning your trip.

Big-O strips away implementation details (constant factors, hardware differences) to reveal the fundamental scalability pattern of an algorithm.

Key Takeaway: Big-O notation is a mathematical framework for expressing the upper bound on how an algorithm's runtime grows relative to input size, focusing on dominant terms and ignoring constant factors.