Algorithms

Junior

Essence

An algorithm is a finite sequence of steps that turns input into output. The same algorithm can be written in any language; in an interview what matters is not the notation but the ability to estimate how time and memory grow with the input.

Asymptotic notation — the most common mistake

• O(f(n)) — upper bound: the algorithm runs no slower than f(n).
• Ω(f(n)) — lower bound: no faster than f(n).
• Θ(f(n)) — tight bound, when the upper and lower bounds coincide.

Worst, best and average case are a different axis. Each of them can be described with any of the three notations. Quicksort, for instance, is Θ(n²) in the worst case and Θ(n log n) on average. In practice people say "O(...)" and mean the worst or average case — ask which one.

Constants and lower-order terms are dropped: 3n² + 100n is O(n²). O(1) means the time does not depend on the input size — a loop of a fixed ten iterations is O(1) too.

Typical classes

• O(1) — index access, lookup in Dictionary/Set.
• O(log n) — binary search in a sorted array.
• O(n) — a linear pass, Array.contains, String.count.
• O(n log n) — sort() / sorted() (since Swift 5: a stable, Timsort-based sort).
• O(n²) — nested loops over the same data.

func binarySearch(_ a: [Int], _ target: Int) -> Int? {
    var lo = 0, hi = a.count - 1
    while lo <= hi {                      // each step halves the range
        let mid = (lo + hi) / 2
        if a[mid] == target { return mid }
        if a[mid] < target { lo = mid + 1 } else { hi = mid - 1 }
    }
    return nil
}
print(binarySearch([1, 3, 5, 7, 9], 7) as Any)   // Optional(3)

// O(n²): for every element we search for a duplicate linearly
func hasDuplicateSlow(_ a: [Int]) -> Bool {
    for i in a.indices {
        for j in a.indices where j != i && a[i] == a[j] { return true }
    }
    return false
}

// O(n): Set.insert reports whether the element was already there
func hasDuplicate(_ a: [Int]) -> Bool {
    var seen = Set<Int>()
    return a.contains { !seen.insert($0).inserted }
}

Space complexity and recursion

Memory is estimated the same way: hasDuplicate spends O(n) on the Set, hasDuplicateSlow spends O(1). Recursion costs O(depth) of stack; Swift does not guarantee tail-call optimisation, so deep recursion (tens of thousands of levels) crashes an iOS app — replace it with a loop.

What the interviewer looks for

• You state the complexity of your solution first, then propose how to improve it (usually: a hash table instead of a nested loop).
• You know the complexities of standard Swift operations, not just the "textbook" structures.