Implementation: Measuring Three Growth Rates

One problem, two complexities: two-sum

Find two indices whose values sum to target. Checking every pair is O(n²); a hash map of seen values makes it one O(n) pass on average.

def two_sum_quadratic(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j
    return None

def two_sum_linear(nums, target):
    seen = {}                        # value -> first index
    for j, x in enumerate(nums):
        i = seen.get(target - x)
        if i is not None:
            return i, j
        seen.setdefault(x, j)
    return None

nums = [8, 3, 11, 5, 2]
print(two_sum_quadratic(nums, 13), two_sum_linear(nums, 13))  # (0, 3) (0, 3)

With several answers, the pairs found may differ.

C++

#include <iostream>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>

using Pair = std::optional<std::pair<int, int>>;

// O(n^2)
Pair twoSumQuadratic(const std::vector<int>& nums, int target) {
    for (std::size_t i = 0; i < nums.size(); ++i)
        for (std::size_t j = i + 1; j < nums.size(); ++j)
            if (nums[i] + nums[j] == target) return std::make_pair(int(i), int(j));
    return std::nullopt;
}

// O(n) average
Pair twoSumLinear(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;  // value -> first index
    for (std::size_t j = 0; j < nums.size(); ++j) {
        auto it = seen.find(target - nums[j]);
        if (it != seen.end()) return std::make_pair(it->second, int(j));
        seen.emplace(nums[j], int(j));
    }
    return std::nullopt;
}

int main() {
    if (auto r = twoSumLinear({8, 3, 11, 5, 2}, 13)) std::cout << r->first << ' ' << r->second << '\n';  // 0 3
}

Java

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    // O(n^2)
    static int[] twoSumQuadratic(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)
                if (nums[i] + nums[j] == target) return new int[] {i, j};
        return null;
    }

    // O(n) average
    static int[] twoSumLinear(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // value -> first index
        for (int j = 0; j < nums.length; j++) {
            Integer i = seen.get(target - nums[j]);
            if (i != null) return new int[] {i, j};
            seen.putIfAbsent(nums[j], j);
        }
        return null;
    }

    public static void main(String[] args) {
        int[] r = twoSumLinear(new int[] {8, 3, 11, 5, 2}, 13);
        System.out.println(r[0] + " " + r[1]);  // 0 3
    }
}

TypeScript

// O(n^2)
function twoSumQuadratic(nums: number[], target: number): [number, number] | null {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return null;
}

// O(n) average
function twoSumLinear(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>(); // value -> first index
  for (let j = 0; j < nums.length; j++) {
    const i = seen.get(target - nums[j]);
    if (i !== undefined) return [i, j];
    if (!seen.has(nums[j])) seen.set(nums[j], j);
  }
  return null;
}

const nums = [8, 3, 11, 5, 2];
console.log(twoSumQuadratic(nums, 13), twoSumLinear(nums, 13)); // [ 0, 3 ] [ 0, 3 ]

Summary

• In a doubling experiment, O(n), O(log n) and O(n²) show up as about 2x, flat and about 4x.
• Time with timeit; keep the minimum of several runs.
• Two-sum trades O(n) memory to turn O(n²) into O(n).