​

Time Complexity

How to measure and reason about algorithm efficiency.

​

Asymptotic Notations

In interviews, Big-O is used almost exclusively.

​

Common Complexities (Ranked)

​

How to Analyze

1. Identify the input size — what is n?
2. Count dominant operations — focus on the innermost loop / recursive calls
3. Drop constants and lower-order terms — 3n² + 5n + 2 → O(n²)
4. Consider all inputs — best, average, and worst case

​

Amortized Analysis

Averages the time per operation over a worst-case sequence of operations (not average case).

​

Example: Dynamic Array (append)

• Most appends are O(1)
• Occasionally the array doubles → O(n) copy
• Over n appends, total work = n + n/2 + n/4 + … ≈ 2n
• Amortized cost per append = O(1)

​

Methods

​

Common Amortized O(1) Operations

• append on dynamic arrays
• push/pop on stacks (even with multipop)
• Union-Find operations (with path compression + union by rank)
• Splay tree operations

​

Recursive Complexity

Use the Master Theorem (see Divide and Conquer page) or draw the recursion tree:

• Linear recursion: T(n) = T(n-1) + O(1) → O(n)
• Binary recursion: T(n) = 2T(n/2) + O(n) → O(n log n)
• Exponential recursion: T(n) = 2T(n-1) + O(1) → O(2^n)

​

Tips for Interviews

• Always state time AND space complexity
• If unsure, trace through a small example and count operations
• Know the complexities of built-in operations (sort, search, insert) for your language
• Mention amortized analysis when relevant (hash maps, dynamic arrays)