Time Complexity Foundation
Algorithm Analysis Foundation Interactive

Time Complexity Foundation

Master Big-O notation and analyze algorithm efficiency. Understand how code scales with input size. Visualize and compare time complexities of common algorithms and data structures.

Theory

Time complexity measures how runtime changes as input size increases. It depends on two things:

  • Input Size (n): The number of elements to process. Larger n = more operations needed.
  • Number of Operations: How many times the code executes. More loops = more operations.
  • Big-O Notation: Describes the upper bound. Ignores constants and lower-order terms.
  • Complexity Classes (from fastest to slowest):
    • O(1) — Constant: No loops, direct access
    • O(log n) — Logarithmic: Halve the search space each iteration
    • O(n) — Linear: Single loop through all elements
    • O(n log n) — Linearithmic: Loop + logarithmic operation per iteration
    • O(n²) — Quadratic: Nested loops
    • O(2ⁿ) — Exponential: Each step doubles the work
  • Key Insight: As input grows, complexity matters more. O(n²) becomes impractical much faster than O(n).

Problem Statement

Understand time complexity through simple loop patterns. Observe how loops determine complexity: 1 loop = O(n), 2 nested = O(n²), halving = O(log n), loop × log = O(n log n). Watch the pseudocode highlight line-by-line as the algorithm executes.

Interactive Complexity Visualizer

Choose Complexity Class

Input Size: 10

Execution Trace

Pseudocode

Statistics

Operations

0

Complexity

O(1)

Formula

f(n) = 1

Step Progress

0 / 0

Complexity Growth Comparison

How Complexity Scales With Input Size

Input Size (n) Operations O(log n) O(n) O(n log n) O(n²)

Complexity Classes

O(1) Constant time, no loops
O(log n) Halve the range each time
O(n) Single loop through all
O(n log n) Loop + halving work each
O(n²) Two nested loops
O(2ⁿ) Each step doubles work

Operations for n=10

O(1) 1
O(log n) 4
O(n) 10
O(n log n) 34
O(n²) 100
O(2ⁿ) 1,024

Notice: Each complexity class creates dramatically different operation counts!

Understanding Loop Patterns

Pattern Code Example Complexity Reason
Halving Loop n = n / 2 each iteration O(log n) Range halves each step (log₂ steps needed)
Single Loop for i in 0..n O(n) Loop runs n times
Loop + Halving for each, halve remaining O(n log n) n iterations × log n work each = n log n
Nested Loops for i in 0..n: for j in 0..n O(n²) n × n iterations = n² total

Key Concepts

Loop Patterns

Halving Pattern

n → n/2 → n/4 → ... = log n steps

Single Loop

Loop runs n times = O(n)

Nested Loops

Loop inside loop = n × n = O(n²)

Loop + Halving

n iterations × log n work = O(n log n)

Why It Matters

Scalability

O(n) processes 1M items. O(n²) takes 1M² times longer!

Choose Wisely

Algorithm choice dramatically impacts performance

Understand Loops

Master loop patterns = master complexity analysis