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.

In easy words

Big-O describes how runtime/memory grow as input size n grows. Focus on the dominant term; ignore constants.

Where this shows up

Choosing algorithms, interview analysis, scaling systems, comparing approaches.

Key facts

  • O(1) - Constant work.
  • O(log n) - Halving each step (binary search).
  • O(n) - Single pass.
  • O(n log n)/O(n^2) - Sorting / nested loops.

What to remember

  • Worst case - Default interview answer.
  • Drop constants - 3n becomes O(n).
  • Space too - Auxiliary memory matters.
  • Input model - What is n? arrays, edges, bits.

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