Complexity Analysis Examples

Math for CS · Axiom Academy

Five detailed analyses from code to Big-O Example 1: Nested Loops with Dependent Bounds Analysis: The inner loop runs i times for each value of i . Total iterations: Example 2: Logarithmic Inner Loop Analysis: The outer loop runs n times. The inner while-loop doubles j each iteration, starting from 1 and stopping when . That takes iterations. Example 3: Recursive Halving with Linear Work Recurrence: Two recursive calls on half the input, plus O(n) work: Master theorem: a = 2, b = 2 , so . The extra work is f(n) = O(n) = O(n^1) . Since , this is Case 2 : Example 4: Two Separate Loops (Not Nested) Analysis: Phase 1 is O(n) . Phase 2 is (since ). Example 5: Amortized — Dynamic Array Append Worst-case single operation: O(n) when we need to resize and copy. Amortized analysis: Resizes happen at sizes . After n appends, total copy cost is: So n appends cost O(n) total, making each append O(1) amortized . Multiply/divide loop variable : iterations Linear loop + log loop nested : Sequential phases : add complexities, dominant term wins Doubling strategy : geometric series sums to O(n) total → O(1) amortized Master theorem : instant answers for T(n) = aT(n/b) + f(n)

This is the written version of the interactive lesson above. See the full Math for CS course.