Time Complexity Foundation
DSA Analysis Foundation

Time Complexity Foundation

What is time complexity

Time complexity describes how runtime grows as input size n grows. Big-O keeps the dominant term and drops constants. One loop is usually O(n). Nested loops are O(n²). Halving each step is O(log n).

  • O(1) / O(log n): constant work, or the search space halves each step.
  • O(n) / O(n log n): one pass, or a pass plus a log-cost step such as sort.
  • O(n²) / O(2ⁿ): nested loops, or work that doubles. These get impractical as n grows.
  • What to report: worst case, what n means, and extra memory — not just the fastest class.

Try it

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