DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master time complexity analysis through 25 carefully chosen worked examples, from single loops to complex recursive algorithms. Each example provides step-by-step analysis, the final Big O answer, and key insights. An essential practice resource for interviews and deeper understanding.
Introduction
Reading about Big O notation and understanding the theory is one thing. Being able to look at any piece of code and immediately determine its time complexity is a different skill — one that only develops through practice.
This lesson provides 25 worked examples, organized from simplest to most complex. For each example, you will see:
- The code
- A step-by-step analysis
- The final Big O answer
- A key insight or pattern to remember
Work through each example yourself before reading the solution. This active engagement is what builds genuine skill.
Example 2 — Print All Pairs (Including Self)
Example
def print_all_pairs(array):
n = len(array)
for i in range(n): # n iterations
for j in range(n): # n iterations per outer
print(array[i], array[j])
Analysis:
- Outer loop: n iterations
- Inner loop: n iterations for each outer iteration
- Total pairs: n × n = n²
- Each pair: O(1) work
Answer: O(n²)
Key insight: Nested loops over the same n-element collection = O(n²).
Example 3 — Print Unique Pairs (Triangle)
Example
def print_unique_pairs(array):
n = len(array)
for i in range(n):
for j in range(i + 1, n): # j starts after i
print(array[i], array[j])
Analysis:
- i=0: j runs from 1 to n-1 → n-1 iterations
- i=1: j runs from 2 to n-1 → n-2 iterations
- i=2: j runs from 3 to n-1 → n-3 iterations
- ...
- i=n-2: j runs from n-1 to n-1 → 1 iteration
- Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2
Answer: O(n²) — the constant factor 1/2 is dropped
Key insight: Triangular iterations (j starts after i) still give O(n²), not O(n²/2).
Example 4 — Two Sequential Loops
python example
def two_passes(array):
# First pass — O(n)
for x in array:
print(x)
# Second pass — O(n)
for x in array:
print(x * 2)Analysis:
- First loop: n iterations
- Second loop: n iterations
- Total: n + n = 2n
Answer: O(n) — the constant 2 is dropped
Key insight: Sequential (non-nested) loops add their complexities. Constants disappear.
Example 5 — Loop with Halving
python example
def count_halvings(n):
count = 0
i = n
while i > 0:
i = i // 2 # Halve i each iteration
count += 1
return countAnalysis:
- Iteration 1: i = n
- Iteration 2: i = n/2
- Iteration 3: i = n/4
- ...
- After k iterations: i = n/2^k
- Loop ends when n/2^k < 1, i.e., 2^k > n, i.e., k > log₂(n)
Answer: O(log n)
Key insight: Any loop that halves (or multiplies by any constant < 1) the controlling variable = O(log n).
Example 6 — Loop with Doubling
python example
def count_doublings(n):
count = 0
i = 1
while i < n:
i = i * 2 # Double i each iteration
count += 1
return countAnalysis:
- Iteration 1: i = 1
- Iteration 2: i = 2
- Iteration 3: i = 4
- ...
- After k iterations: i = 2^k
- Loop ends when 2^k ≥ n, i.e., k ≥ log₂(n)
Answer: O(log n)
Key insight: Same as halving but in the other direction. Both doubling and halving give O(log n).
Intermediate Examples — Mixed Patterns
Example 7 — Mixed Complexity
Example
def mixed_algorithm(array):
n = len(array)
# Block A: O(n²)
for i in range(n):
for j in range(n):
print(array[i] + array[j])
# Block B: O(n)
for x in array:
print(x)
# Block C: O(log n)
i = 1
while i < n:
i *= 2
Analysis:
- Block A: O(n²)
- Block B: O(n)
- Block C: O(log n)
- Total: O(n²) + O(n) + O(log n)
- Dominant term: n²
Answer: O(n²)
Key insight: When adding complexities, keep only the dominant term.
Example 8 — Inner Loop Depends on Outer
python example
def triangle_sum(n):
total = 0
for i in range(n):
for j in range(i): # j goes from 0 to i-1
total += 1
return totalAnalysis:
- i=0: 0 iterations (j from 0 to -1, loop doesn't run)
- i=1: 1 iteration
- i=2: 2 iterations
- ...
- i=n-1: n-1 iterations
- Total: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2
Answer: O(n²)
Key insight: Even when the inner loop bound depends on the outer variable, if it results in a triangular sum, the complexity is O(n²).
Example 9 — Logarithmic Inner Loop
python example
def log_inner(array):
n = len(array)
for i in range(n): # n iterations
j = 1
while j < n: # log n iterations
j *= 2Analysis:
- Outer loop: n iterations
- Inner loop: log n iterations (doubling)
- Total: n × log n
Answer: O(n log n)
Key insight: A loop of n iterations, each containing a log n inner loop = O(n log n). This is the pattern of many efficient algorithms.
Example 10 — Constant Work in Nested Function
python example
def outer_calls_binary_search(array):
"""For each element, check if it exists in the sorted array."""
sorted_arr = sorted(array) # O(n log n) preprocessing
for x in array: # n iterations
result = binary_search(sorted_arr, x) # O(log n) each
print(result)
# binary_search is O(log n)Analysis:
- Preprocessing: O(n log n)
- Loop: n × O(log n) = O(n log n)
- Total: O(n log n) + O(n log n) = O(2 × n log n)
Answer: O(n log n)
Key insight: Calling an O(log n) function inside an O(n) loop = O(n log n).
Example 11 — Different Input Sizes
python example
def process_two_arrays(a, b):
"""
a and b are arrays with different sizes m and n.
"""
for x in a: # m iterations
for y in b: # n iterations
print(x, y)Analysis:
- This is NOT O(n²)
- The inputs have different sizes: m = len(a), n = len(b)
- Total: m × n iterations
Answer: O(m × n)
If m = n, this simplifies to O(n²). But if they are different (e.g., m = 10, n = 1,000,000), calling it O(n²) is wrong.
Key insight: Use different variables for genuinely different input sizes.
Example 12 — Fibonacci without Memoization
python example
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)Analysis:
Example
Recursion tree for fibonacci(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)
Each call makes 2 calls. Depth = n. Total nodes ≈ 2ⁿ.
Answer: O(2ⁿ)
Key insight: Two recursive calls on inputs of size n-1 and n-2 (not n/2!) = exponential.
Example 13 — Fibonacci with Memoization
Example
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n] # O(1) lookup
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
Analysis:
- Each unique value of n is computed exactly once
- Unique values: 0, 1, 2, ..., n → n+1 values
- Each computation: O(1) (just one addition after sub-results are cached)
- Total: (n+1) × O(1)
Answer: O(n)
Key insight: Memoization eliminates recomputation. The complexity becomes (number of unique subproblems) × (work per subproblem).
Advanced Examples — Recursion and Complex Patterns
Example 14 — Merge Sort
Example
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left = merge_sort(array[:mid]) # T(n/2)
right = merge_sort(array[mid:]) # T(n/2)
return merge(left, right) # O(n) merge
Recurrence: T(n) = 2T(n/2) + n
Analysis via recursion tree:
| Level 0: 1 subproblem of size n | n work |
| Level 1: 2 subproblems of n/2 | n/2 + n/2 = n work |
| Level 2: 4 subproblems of n/4 | n work |
| Level log n: n subproblems of 1 | n × O(1) = n work |
| Levels | log n + 1 |
| Work per level | n |
| Total | n × (log n + 1) ≈ n log n |
Answer: O(n log n)
Example 15 — Power Function (Naive)
python example
def power_naive(base, exponent):
if exponent == 0:
return 1
return base * power_naive(base, exponent - 1)Analysis:
- Each call reduces exponent by 1
- Starting from exponent, ending at 0
- Total calls: exponent + 1
Answer: O(n) where n = exponent
Example 16 — Power Function (Fast Exponentiation)
python example
def power_fast(base, exponent):
if exponent == 0:
return 1
if exponent % 2 == 0:
half = power_fast(base, exponent // 2) # Halves exponent!
return half * half
else:
return base * power_fast(base, exponent - 1)Analysis:
- When exponent is even: recurse with exponent/2 (halving)
- When exponent is odd: one decrement, then next call will halve
- Maximum halvings from n to 1: log₂(n)
- Each halving can be preceded by at most one decrement
Answer: O(log n) — Binary Exponentiation
Key insight: Halving the input at each recursive step = O(log n), even with occasional +1 decrements.
Example 17 — Tower of Hanoi
python example
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target) # Move n-1 disks to auxiliary
print(f"Move disk {n} from {source} to {target}")
hanoi(n - 1, auxiliary, target, source) # Move n-1 disks to targetRecurrence: T(n) = 2T(n-1) + 1
Solving by expansion:
Example
T(n) = 2T(n-1) + 1
= 2(2T(n-2) + 1) + 1 = 4T(n-2) + 2 + 1
= 4(2T(n-3) + 1) + 3 = 8T(n-3) + 4 + 2 + 1
= 2^k × T(n-k) + (2^k - 1)
Set k = n-1:
T(n) = 2^(n-1) × T(1) + 2^(n-1) - 1
= 2^(n-1) + 2^(n-1) - 1
= 2^n - 1
Answer: O(2ⁿ)
Key insight: Two recursive calls on input n-1 (not n/2) = exponential growth.
Example 18 — All Subsets of an Array
Example
def generate_subsets(array, index=0, current=[]):
if index == len(array):
print(current)
return
# Include array[index]
generate_subsets(array, index + 1, current + [array[index]])
# Exclude array[index]
generate_subsets(array, index + 1, current)
Analysis:
- At each index position, we make 2 choices (include or exclude)
- n positions × 2 choices each = 2ⁿ total subsets
- Each subset takes O(n) to process (creating a copy)
Answer: O(n × 2ⁿ)
Key insight: Generating all subsets requires O(2ⁿ) time — you cannot do it faster.
Example 19 — All Permutations
Example
def generate_permutations(array, start=0):
if start == len(array):
print(array.copy())
return
for i in range(start, len(array)):
array[start], array[i] = array[i], array[start] # Swap
generate_permutations(array, start + 1)
array[start], array[i] = array[i], array[start] # Swap back
Analysis:
- At position 0: n choices
- At position 1: n-1 choices (already placed one element)
- At position 2: n-2 choices
- ...
- Total: n × (n-1) × (n-2) × ... × 1 = n!
Answer: O(n! × n) — n! permutations, each taking O(n) to record
Key insight: Permutations grow factorially. Even n=20 gives over 2 quadrillion permutations.
Example 20 — Graph BFS (Breadth-First Search)
Example
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft() # O(1)
print(node)
for neighbor in graph[node]: # Process all edges of this node
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Analysis:
- Each vertex is enqueued and dequeued at most once: O(V) total
- For each vertex, we process all its edges: total edge processing = O(E)
- Total: O(V + E)
Answer: O(V + E) where V = vertices, E = edges
Key insight: Graph algorithms typically depend on both the number of vertices AND edges. O(V + E) is the standard for BFS and DFS.
Example 21 — Matrix Multiply (Naive)
Example
def matrix_multiply(A, B, n):
"""Multiply two n×n matrices."""
C = [[0] * n for _ in range(n)]
for i in range(n): # n iterations
for j in range(n): # n iterations
for k in range(n): # n iterations
C[i][j] += A[i][k] * B[k][j]
return C
Analysis:
- Three nested loops, each running n times
- Total: n × n × n = n³
Answer: O(n³)
Key insight: Triple nested loops with the same bound = O(n³). Strassen's algorithm reduces this to O(n^2.807) using clever decomposition.
Example 22 — Detect Cycle in Linked List (Floyd's Algorithm)
python example
def has_cycle(head):
"""Floyd's tortoise and hare algorithm."""
if not head:
return False
slow = head # Moves 1 step at a time
fast = head # Moves 2 steps at a time
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseAnalysis:
- Both pointers move forward through the list
- If there's a cycle of length c, fast catches slow in O(c) steps after both enter the cycle
- Total nodes visited: proportional to the list length n
Answer: O(n)
Key insight: Even though two pointers move at different speeds, the total traversal is bounded by O(n).
Example 23 — Binary Search on Answer
Example
def min_speed_to_arrive(dist, hour):
"""
Binary search on the answer space.
Checks if a given speed allows arrival by 'hour'.
"""
def can_arrive(speed):
time = 0
for i in range(len(dist) - 1):
time += math.ceil(dist[i] / speed) # Round up each segment
time += dist[-1] / speed # Last segment, no rounding
return time <= hour
left, right = 1, 10**7 # Search space for speed
while left < right: # O(log(max_speed)) iterations
mid = (left + right) // 2
if can_arrive(mid):
right = mid
else:
left = mid + 1
return left
Analysis:
- Binary search on speed from 1 to 10^7: log(10^7) ≈ 23 iterations
- Each check: O(n) where n = len(dist)
- Total: O(n log(max_speed))
Answer: O(n log S) where S = maximum speed
Key insight: "Binary Search on Answer" is a powerful technique where you binary search over the answer space and for each candidate answer, verify it in O(n). Total: O(n log range).
Example 24 — Sliding Window Maximum
Example
from collections import deque
def sliding_window_maximum(array, k):
"""Find maximum in each window of size k."""
result = []
deque_q = deque() # Stores indices, maintains decreasing order of values
for i in range(len(array)):
# Remove elements outside the window
while deque_q and deque_q[0] < i - k + 1:
deque_q.popleft()
# Remove smaller elements (they can never be the max)
while deque_q and array[deque_q[-1]] < array[i]:
deque_q.pop()
deque_q.append(i)
if i >= k - 1:
result.append(array[deque_q[0]])
return result
Analysis:
- Each element is added to the deque exactly once: O(n) additions
- Each element is removed from the deque at most once: O(n) removals
- Total operations on deque: O(2n) = O(n)
- Main loop: n iterations
Answer: O(n) — linear despite the while loops inside
Key insight: Amortized analysis — "at most once" operations inside loops make the total O(n) even when loops appear to suggest otherwise.
Example 25 — Finding Number of Inversions (Merge Sort Based)
Example
def count_inversions(array):
"""
An inversion is a pair (i, j) where i < j but array[i] > array[j].
Uses modified Merge Sort.
"""
if len(array) <= 1:
return array, 0
mid = len(array) // 2
left, left_inv = count_inversions(array[:mid]) # T(n/2)
right, right_inv = count_inversions(array[mid:]) # T(n/2)
merged, split_inv = merge_and_count(left, right) # O(n)
return merged, left_inv + right_inv + split_inv
def merge_and_count(left, right):
result = []
inversions = 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
inversions += len(left) - i # All remaining left elements form inversions
result.extend(left[i:])
result.extend(right[j:])
return result, inversions
Analysis:
- This is Merge Sort with one extra O(1) operation per comparison
- Recurrence: T(n) = 2T(n/2) + O(n) — same as Merge Sort
Answer: O(n log n)
Key insight: Augmenting Merge Sort with additional O(1) work per step preserves the O(n log n) complexity.
Quick Reference — Pattern to Complexity
| Code Pattern | Complexity | Example Algorithm |
|---|---|---|
| Single loop over n | O(n) | Linear search |
| Two nested loops over n | O(n²) | Bubble sort |
| Triple nested loops over n | O(n³) | Naive matrix multiply |
| Loop halving/doubling | O(log n) | Binary search |
| Loop + halving inner loop | O(n log n) | Most efficient sorts |
| Recursive, halves input | O(log n) | Binary search recursive |
| Recursive, two calls halving | O(n log n) | Merge sort |
| Recursive, two calls subtracting 1 | O(2ⁿ) | Naive Fibonacci |
| Recursive, memoized | O(unique states) | DP Fibonacci |
| All subsets | O(n × 2ⁿ) | Power set generation |
| All permutations | O(n × n!) | Permutation generation |
| Graph BFS/DFS | O(V + E) | Traversal |
Summary
Analyzing time complexity is a skill developed through practice. The key rules to remember:
- Drop constants: O(3n) = O(n)
- Keep dominant term: O(n² + n) = O(n²)
- Sequential blocks add: O(n) + O(n) = O(n)
- Nested blocks multiply: O(n) × O(n) = O(n²)
- Halving loop: O(log n)
- Loop + inner halving: O(n log n)
- Two recursive calls on n-1: O(2ⁿ)
- Two recursive calls on n/2 + O(n) work: O(n log n)
- Memoization: (unique states) × (work per state)
- Graph algorithms: O(V + E)
Practice these 25 examples until the analysis becomes automatic. At that point, you are ready to handle any complexity analysis question in an interview.
*This completes the Algorithm Analysis section. Next section: Arrays — The most fundamental data structure, the foundation of all linear storage.*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Time Complexity Examples — 25 Worked Problems from Basic to Advanced.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, algorithm, analysis, time
Related Data Structures & Algorithms Topics
Continue learning this concept
Algorithm AnalysisSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsA complete guide to space complexity analysis — what counts as auxiliary space, how to analyze iterative and recursive algorithms, how recursion creates implicit stack space, common space complexity classes with examples, and the fundamental time-space tradeoffs every programmer must understand.Algorithm AnalysisAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremMaster asymptotic analysis — the complete mathematical framework for analyzing algorithm complexity. Learn to solve recurrence relations using the substitution method, recursion tree method, and Master Theorem. Includes full worked examples for all common algorithm patterns.Algorithm AnalysisBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmLearn how to perform best, average, and worst case analysis for any algorithm. Understand why input matters, how to identify the best and worst inputs for common algorithms, and when each type of analysis is most useful — with detailed worked examples for searching, sorting, and more.Algorithm AnalysisBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesMaster Big O notation with the formal mathematical definition, the four rules for simplifying complexity expressions, step-by-step worked examples, common patterns to recognize instantly, and a comprehensive reference table for every major algorithm.Algorithm AnalysisBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionLearn Big Omega (Ω) notation — the formal lower bound for algorithm complexity. Understand what best-case analysis means, why lower bounds matter in algorithm design, and how Omega complements Big O in a complete complexity analysis.Algorithm AnalysisBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesMaster Big Theta notation — the tightest and most precise way to characterize algorithm complexity. Learn the formal definition, understand when Theta applies, see detailed examples, and learn how Theta relates to Big O and Big Omega to give a complete complexity picture.