Chapter 2: Complexity Analysis Essentials

---

"Your solution works, but what's the time complexity?"

This question comes up in every coding interview. If you stumble here, it signals a gap in your fundamentals—even if your code is correct. This chapter gives you everything you need to analyze and communicate the efficiency of your solutions confidently.

---

Why Complexity Analysis Matters

As mobile developers, we think about performance constantly. Will this API call block the main thread? How fast can we render this list? Should we cache this computation?

Complexity analysis is the formal language for answering these questions. It lets you:

• Compare solutions — Is approach A faster than approach B?
• Predict scalability — Will this work with 10,000 items? 1,000,000?
• Communicate precisely — "It's O(n log n)" is clearer than "it's pretty fast"
• Satisfy interviewers — They expect you to analyze your own code

You don't need a computer science degree to master this. You need to understand a few core concepts and practice applying them.

---

Big O Notation: The Basics

Big O notation describes how an algorithm's performance scales as input size grows. It answers: "If I double the input, what happens to the runtime?"

The Key Insight

Big O ignores constants and focuses on the dominant term. Why? Because when your input grows from 1,000 to 1,000,000 items, the difference between O(n) and O(n²) matters far more than whether your O(n) algorithm takes 2n or 5n operations.

O(2n + 100) → O(n)
O(n² + n + 1000) → O(n²)
O(500) → O(1)

We care about the shape of growth, not the exact numbers.

Reading Big O

When you see O(n):

• n represents the input size
• The expression inside describes how operations scale with n
• "O" means "on the order of" (upper bound)

O(n) means: as input doubles, runtime roughly doubles. O(n²) means: as input doubles, runtime roughly quadruples. O(log n) means: as input doubles, runtime increases by a constant amount.

---

Common Complexity Classes

Here are the complexity classes you'll encounter constantly, ordered from fastest to slowest.

O(1) — Constant Time

Runtime doesn't change regardless of input size.

// Swift
func getFirst(_ array: [Int]) -> Int? {
    return array.first  // O(1)
}

func accessHashMap(_ dict: [String: Int], key: String) -> Int? {
    return dict[key]  // O(1) average
}

// Kotlin
fun getFirst(array: List<Int>): Int? {
    return array.firstOrNull()  // O(1)
}

fun accessHashMap(map: Map<String, Int>, key: String): Int? {
    return map[key]  // O(1) average
}

Examples: Array access by index, hash map lookup, push/pop on a stack, checking if a number is even.

Interview tip: When you achieve O(1) for a key operation, mention it. "Hash map gives us O(1) lookup here."

---

O(log n) — Logarithmic Time

Runtime grows by a constant amount each time input doubles. This usually means you're cutting the problem in half at each step.

// Swift
func binarySearch(_ array: [Int], target: Int) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return nil  // O(log n)
}

// Kotlin
fun binarySearch(array: IntArray, target: Int): Int? {
    var left = 0
    var right = array.size - 1
    
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            array[mid] == target -> return mid
            array[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return null  // O(log n)
}

Examples: Binary search, operations on balanced BST, finding an element in a sorted rotated array.

The math: log₂(1,000,000) ≈ 20. Even with a million elements, you need only ~20 steps. This is why binary search is powerful.

---

O(n) — Linear Time

Runtime grows proportionally with input. You typically visit each element once.

// Swift
func findMax(_ array: [Int]) -> Int? {
    guard !array.isEmpty else { return nil }
    var maxVal = array[0]
    for num in array {
        maxVal = max(maxVal, num)
    }
    return maxVal  // O(n)
}

func twoSumWithHashMap(_ nums: [Int], target: Int) -> [Int]? {
    var seen = [Int: Int]()
    for (i, num) in nums.enumerated() {
        let complement = target - num
        if let j = seen[complement] {
            return [j, i]
        }
        seen[num] = i
    }
    return nil  // O(n)
}

// Kotlin
fun findMax(array: IntArray): Int? {
    if (array.isEmpty()) return null
    var maxVal = array[0]
    for (num in array) {
        maxVal = maxOf(maxVal, num)
    }
    return maxVal  // O(n)
}

fun twoSumWithHashMap(nums: IntArray, target: Int): IntArray? {
    val seen = mutableMapOf<Int, Int>()
    for ((i, num) in nums.withIndex()) {
        val complement = target - num
        seen[complement]?.let { j ->
            return intArrayOf(j, i)
        }
        seen[num] = i
    }
    return null  // O(n)
}

Examples: Finding max/min, linear search, most single-pass array problems, hash map construction.

Interview tip: O(n) is often the optimal solution for array problems. If your first instinct is O(n²), ask yourself: "Can I use a hash map to bring this down to O(n)?"

---

O(n log n) — Linearithmic Time

Common in efficient sorting algorithms and divide-and-conquer approaches.

// Swift
func sortArray(_ array: [Int]) -> [Int] {
    return array.sorted()  // O(n log n)
}

// Merge Sort implementation
func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    
    let mid = array.count / 2
    let left = mergeSort(Array(array[0..<mid]))
    let right = mergeSort(Array(array[mid...]))
    
    return merge(left, right)  // O(n log n) total
}

// Kotlin
fun sortArray(array: IntArray): IntArray {
    return array.sortedArray()  // O(n log n)
}

// Merge Sort implementation
fun mergeSort(array: IntArray): IntArray {
    if (array.size <= 1) return array
    
    val mid = array.size / 2
    val left = mergeSort(array.sliceArray(0 until mid))
    val right = mergeSort(array.sliceArray(mid until array.size))
    
    return merge(left, right)  // O(n log n) total
}

Examples: Merge sort, quicksort (average case), heap sort, many divide-and-conquer algorithms.

The intuition: You're doing O(n) work at each of O(log n) levels of recursion.

---

O(n²) — Quadratic Time

Runtime grows with the square of input. Usually involves nested loops over the same data.

// Swift
func bubbleSort(_ array: inout [Int]) {
    let n = array.count
    for i in 0..<n {
        for j in 0..<(n - i - 1) {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
    // O(n²)
}

func twoSumBruteForce(_ nums: [Int], target: Int) -> [Int]? {
    for i in 0..<nums.count {
        for j in (i + 1)..<nums.count {
            if nums[i] + nums[j] == target {
                return [i, j]
            }
        }
    }
    return nil  // O(n²)
}

// Kotlin
fun bubbleSort(array: IntArray) {
    val n = array.size
    for (i in 0 until n) {
        for (j in 0 until n - i - 1) {
            if (array[j] > array[j + 1]) {
                val temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
            }
        }
    }
    // O(n²)
}

fun twoSumBruteForce(nums: IntArray, target: Int): IntArray? {
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] + nums[j] == target) {
                return intArrayOf(i, j)
            }
        }
    }
    return null  // O(n²)
}

Examples: Bubble sort, insertion sort, brute force pair finding, comparing all pairs.

Interview warning: O(n²) is often the "naive" solution that interviewers expect you to optimize. When you present an O(n²) approach, immediately follow with: "But I think we can do better with..."

---

O(2ⁿ) — Exponential Time

Runtime doubles with each additional input element. Common in recursive solutions without memoization.

// Swift
func fibonacciNaive(_ n: Int) -> Int {
    if n <= 1 { return n }
    return fibonacciNaive(n - 1) + fibonacciNaive(n - 2)  // O(2ⁿ)
}

// All subsets of an array
func subsets(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    
    func backtrack(_ index: Int, _ current: [Int]) {
        result.append(current)
        for i in index..<nums.count {
            backtrack(i + 1, current + [nums[i]])
        }
    }
    
    backtrack(0, [])
    return result  // O(2ⁿ) subsets generated
}

// Kotlin
fun fibonacciNaive(n: Int): Int {
    if (n <= 1) return n
    return fibonacciNaive(n - 1) + fibonacciNaive(n - 2)  // O(2ⁿ)
}

// All subsets of an array
fun subsets(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    
    fun backtrack(index: Int, current: MutableList<Int>) {
        result.add(current.toList())
        for (i in index until nums.size) {
            current.add(nums[i])
            backtrack(i + 1, current)
            current.removeAt(current.size - 1)
        }
    }
    
    backtrack(0, mutableListOf())
    return result  // O(2ⁿ) subsets generated
}

Examples: Naive Fibonacci, generating all subsets, some backtracking problems without pruning.

Interview tip: When you see exponential complexity, ask yourself: "Can dynamic programming or memoization help?"

---

O(n!) — Factorial Time

The slowest common complexity. Runtime grows factorially—n! = n × (n-1) × (n-2) × ... × 1.

// Swift
func permutations(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    var used = [Bool](repeating: false, count: nums.count)
    
    func backtrack(_ current: [Int]) {
        if current.count == nums.count {
            result.append(current)
            return
        }
        for i in 0..<nums.count {
            if used[i] { continue }
            used[i] = true
            backtrack(current + [nums[i]])
            used[i] = false
        }
    }
    
    backtrack([])
    return result  // O(n!)
}

// Kotlin
fun permutations(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val used = BooleanArray(nums.size)
    
    fun backtrack(current: MutableList<Int>) {
        if (current.size == nums.size) {
            result.add(current.toList())
            return
        }
        for (i in nums.indices) {
            if (used[i]) continue
            used[i] = true
            current.add(nums[i])
            backtrack(current)
            current.removeAt(current.size - 1)
            used[i] = false
        }
    }
    
    backtrack(mutableListOf())
    return result  // O(n!)
}

Examples: Generating all permutations, traveling salesman (brute force), some constraint satisfaction problems.

Reality check: 10! = 3,628,800. 20! ≈ 2.4 quintillion. Factorial algorithms only work for very small inputs.

---

Complexity Comparison Table

Big O	Name	n=10	n=100	n=1000	n=10000
O(1)	Constant	1	1	1	1
O(log n)	Logarithmic	3	7	10	13
O(n)	Linear	10	100	1,000	10,000
O(n log n)	Linearithmic	33	664	9,966	132,877
O(n²)	Quadratic	100	10,000	1,000,000	100,000,000
O(2ⁿ)	Exponential	1,024	10³⁰	∞	∞
O(n!)	Factorial	3,628,800	∞	∞	∞

Use this table to sanity-check your solutions. If your algorithm is O(n²) and n can be 100,000, that's 10 billion operations—probably too slow.

---

Space Complexity

Time isn't everything. Space complexity measures how much additional memory your algorithm uses as input grows.

Key Distinction: Input vs Auxiliary Space

Total space = Input space + Auxiliary space

Usually, we care about auxiliary space—the extra memory beyond the input itself.

// Swift

// O(1) auxiliary space - modifies array in place
func reverseInPlace(_ array: inout [Int]) {
    var left = 0
    var right = array.count - 1
    while left < right {
        array.swapAt(left, right)
        left += 1
        right -= 1
    }
}

// O(n) auxiliary space - creates new array
func reverseWithCopy(_ array: [Int]) -> [Int] {
    return array.reversed()  // Creates new array
}

// Kotlin

// O(1) auxiliary space - modifies array in place
fun reverseInPlace(array: IntArray) {
    var left = 0
    var right = array.size - 1
    while (left < right) {
        val temp = array[left]
        array[left] = array[right]
        array[right] = temp
        left++
        right--
    }
}

// O(n) auxiliary space - creates new array
fun reverseWithCopy(array: IntArray): IntArray {
    return array.reversedArray()  // Creates new array
}

Common Space Complexities

O(1) Space:

• Using a fixed number of variables
• In-place array modifications
• Two-pointer techniques

O(n) Space:

• Creating a hash map of input elements
• Building a result array
• Recursion stack for linear recursion depth

O(n²) Space:

• 2D matrix for DP
• Adjacency matrix for graphs

Recursion and Stack Space

Every recursive call adds a frame to the call stack. This counts toward space complexity.

// Swift
func factorial(_ n: Int) -> Int {
    if n <= 1 { return 1 }
    return n * factorial(n - 1)
    // O(n) space due to recursion depth
}

func factorialIterative(_ n: Int) -> Int {
    var result = 1
    for i in 2...n {
        result *= i
    }
    return result
    // O(1) space
}

// Kotlin
fun factorial(n: Int): Int {
    if (n <= 1) return 1
    return n * factorial(n - 1)
    // O(n) space due to recursion depth
}

fun factorialIterative(n: Int): Int {
    var result = 1
    for (i in 2..n) {
        result *= i
    }
    return result
    // O(1) space
}

Interview tip: When discussing recursive solutions, always mention the stack space. "This is O(n) time and O(n) space due to the recursion depth."

---

Analyzing Your Own Code

Here's a systematic approach to determine complexity:

Step 1: Identify the Input Size Variable

What is "n"? Usually it's array length, string length, or number of nodes. Sometimes you have multiple variables (e.g., n rows and m columns).

Step 2: Count the Loops

Loop Structure	Complexity
Single loop over n elements	O(n)
Nested loops, both over n	O(n²)
Loop that halves the range each time	O(log n)
Loop over n, inner loop over m	O(n × m)

Step 3: Account for Built-in Operations

Don't forget hidden costs:

Operation	Swift	Kotlin	Complexity
Sort	array.sorted()	array.sorted()	O(n log n)
Contains (array)	array.contains(x)	x in array	O(n)
Contains (set)	set.contains(x)	x in set	O(1)
Insert at start	array.insert(x, at: 0)	list.add(0, x)	O(n)
String concatenation in loop	str += char	str += char	O(n) per operation

Step 4: Analyze Recursive Functions

For recursion, use the recurrence relation:

Example: Binary search

T(n) = T(n/2) + O(1)

Halving each time with constant work = O(log n)

Example: Merge sort

T(n) = 2T(n/2) + O(n)

Two subproblems of half size plus linear merge = O(n log n)

Example: Naive Fibonacci

T(n) = T(n-1) + T(n-2) + O(1)

Two subproblems of nearly same size = O(2ⁿ)

---

Common Patterns and Their Complexities

Memorize these—they come up constantly:

Pattern	Time	Space	Example
Two Pointers	O(n)	O(1)	Container with most water
Sliding Window	O(n)	O(k)	Longest substring with k distinct chars
Binary Search	O(log n)	O(1)	Search in rotated array
BFS/DFS on graph	O(V + E)	O(V)	Number of islands
BFS/DFS on tree	O(n)	O(h)	Max depth of tree
Dynamic Programming	O(n × m)	O(n × m) or O(n)	Longest common subsequence
Backtracking	O(k^n) or O(n!)	O(n)	Permutations, subsets
Heap operations	O(log n) per op	O(n)	Top K elements
Sorting-based	O(n log n)	O(n) or O(1)	Merge intervals

---

Talking About Complexity in Interviews

Interviewers want to hear you analyze complexity unprompted. Here's how to do it naturally:

Before Coding

"Before I code this, let me think about complexity. The brute force would be O(n²) because we'd check every pair. But if we use a hash map, we can do it in O(n) time and O(n) space."

After Coding

"Let me analyze this solution. We iterate through the array once, and each hash map operation is O(1), so overall time is O(n). We store at most n elements in the hash map, so space is O(n)."

When Asked to Optimize

"The current solution is O(n²). The bottleneck is the nested loop where we search for the complement. If we sort the array first, we can use two pointers to bring it down to O(n log n). Or with a hash map, we can achieve O(n)."

Handling Trade-offs

"We have two options here. The iterative approach uses O(1) space but requires more complex code. The recursive approach is cleaner but uses O(n) stack space. Which would you prefer I implement?"

---

Quick Reference Card

Print this or keep it handy during practice:

COMPLEXITY CHEAT SHEET

TIME COMPLEXITY (fastest to slowest):
O(1)       → Hash lookup, array access
O(log n)   → Binary search, balanced BST
O(n)       → Single pass, hash map build
O(n log n) → Efficient sorts, divide & conquer
O(n²)      → Nested loops, brute force pairs
O(2ⁿ)      → Subsets, naive recursion
O(n!)      → Permutations

SPACE COMPLEXITY:
O(1)       → Fixed variables, in-place
O(log n)   → Balanced recursion depth
O(n)       → Hash map, result array, linear recursion
O(n²)      → 2D DP matrix

RED FLAGS:
- Nested loops over same data → O(n²), can you use hash map?
- String += in loop → O(n²) total, use array/builder
- Recursion without memo → Exponential, add caching
- Sorting when not needed → Unnecessary O(n log n)

QUICK WINS:
- Hash map turns O(n²) lookup into O(n)
- Sorting enables O(n) two-pointer solutions
- Heap gives O(n log k) for top-k problems
- Memoization turns O(2ⁿ) into O(n) for DP

---

Practice Problems

Before moving to pattern chapters, verify your complexity analysis skills with these exercises.

Exercise 1: What's the time and space complexity?

func mystery(_ n: Int) -> Int {
    var result = 0
    for i in 0..<n {
        for j in i..<n {
            result += 1
        }
    }
    return result
}

Answer

Time: O(n²) — The inner loop runs n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times. Space: O(1) — Only using fixed variables.

Exercise 2: What's the time and space complexity?

fun mystery(n: Int): List<Int> {
    val result = mutableListOf<Int>()
    var i = n
    while (i > 0) {
        result.add(i)
        i /= 2
    }
    return result
}

Answer

Time: O(log n) — We halve i each iteration. Space: O(log n) — We store log n elements in the result list.

Exercise 3: What's the time and space complexity?

func mystery(_ s: String) -> String {
    var result = ""
    for char in s {
        result = String(char) + result
    }
    return result
}

Answer

Time: O(n²) — String prepending creates a new string each time, and each creation is O(current length). Space: O(n) — The result string grows to length n.

---

What's Next

You now have the vocabulary to analyze any solution. As you work through pattern chapters, practice analyzing complexity for every problem—even before reading the solution.

In the next chapter, we begin our first pattern: Two Pointers. This foundational technique will transform how you approach array and string problems.

---

Continue to Chapter 3: Two Pointers →