Course contentsShow
← Software Engineering
Lesson 1192 of 1,93336. Performance EngineeringFree lesson

Big-O Notation and Algorithmic Complexity

Reviewing time and space complexity to understand the scalability characteristics of algorithms and data structures.

Big-O Notation and Algorithmic Complexity

What you'll learn: How to describe and compare the scalability characteristics of algorithms using Big-O notation.

Understanding Algorithmic Complexity

When evaluating performance, we need a standard way to describe how an algorithm's resource consumption grows as input size increases. Big-O notation provides this language, expressing the worst-case growth rate of time or space requirements.

Big-O focuses on the dominant factor as input size (n) approaches infinity, ignoring constants and smaller terms. An algorithm that takes 3n² + 5n + 10 operations is classified as O(n²) because the quadratic term dominates at scale.

Common Complexity Classes

Here are typical complexities from fastest to slowest:

  • O(1) – Constant: Array index access
  • O(log n) – Logarithmic: Binary search
  • O(n) – Linear: Single loop through data
  • O(n log n) – Linearithmic: Efficient sorting (merge sort)
  • O(n²) – Quadratic: Nested loops
  • O(2ⁿ) – Exponential: Recursive fibonacci (naive)

Time vs Space Complexity

Big-O applies to both dimensions:

  • Time complexity: How execution time scales
  • Space complexity: How memory usage scales

A hash table lookup might be O(1) time but O(n) space. Understanding both helps you make informed trade-offs between speed and memory.

The Scalability Lens

Big-O reveals what happens when your system grows from 100 to 100,000 users. An O(n²) algorithm processing 100 items takes 10,000 operations; at 1,000 items, it takes 1,000,000 operations—a 100× input yields 10,000× work. This makes Big-O essential for predicting production behavior.

Key Takeaway: Big-O notation describes how algorithms scale by expressing the growth rate of resource consumption relative to input size, helping you predict performance at scale and choose appropriate data structures and algorithms.