Big-O Notation

// JavaScript
function getFirst(arr) {
  return arr[0];
}

const map = new Map();
map.set('key', 42);
map.get('key'); // O(1) average

# Python
def get_first(arr):
    return arr[0]

lookup = {'key': 42}
lookup['key']  # O(1) average

// JavaScript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

// JavaScript
function findMax(arr) {
  let max = -Infinity;
  for (const val of arr) {
    if (val > max) max = val;
  }
  return max;
}

# Python
def find_max(arr):
    maximum = float('-inf')
    for val in arr:
        if val > maximum:
            maximum = val
    return maximum

// JavaScript
// Merge sort achieves O(n log n) guaranteed
const sorted = [5, 2, 8, 1, 9].sort((a, b) => a - b);
// Built-in sort: V8 uses TimSort → O(n log n)

# Python
# Python's sorted() uses TimSort → O(n log n)
result = sorted([5, 2, 8, 1, 9])
# list.sort() is in-place, also O(n log n)

// JavaScript
function hasDuplicateBrute(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

# Python
def has_duplicate_brute(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

// JavaScript
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}
// Each call branches into 2 → O(2^n)

# Python
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Fix with memoization → O(n)

// JavaScript
function permutations(arr) {
  if (arr.length <= 1) return [arr];
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const perm of permutations(rest)) {
      result.push([arr[i], ...perm]);
    }
  }
  return result;
}

# Python
def get_permutations(arr):
    if len(arr) <= 1:
        return [arr[:]]
    result = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for perm in get_permutations(rest):
            result.append([arr[i]] + perm)
    return result

// JavaScript — Analyzing a function
function example(arr) {
  // Loop 1: O(n)
  for (let i = 0; i < arr.length; i++) { /* ... */ }
  // Loop 2 (nested): O(n^2)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { /* ... */ }
  }
}
// Total: O(n) + O(n^2) = O(n^2) — dominated by the larger term

# Python — Same analysis
def example(arr):
    for x in arr:        # O(n)
        pass
    for x in arr:        # O(n^2)
        for y in arr:
            pass
# Total: O(n^2)

// JavaScript
// O(1) space — in-place swap
function reverseInPlace(arr) {
  let l = 0, r = arr.length - 1;
  while (l < r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
    l++; r--;
  }
}

// O(n) space — new array
function reversed(arr) {
  return arr.slice().reverse();
}

# Python
def reverse_in_place(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]
        l += 1; r -= 1

def reversed_copy(arr):
    return arr[::-1]  # O(n) space

// JavaScript
// Dynamic array (push) — occasionally resizes (O(n) copy)
// but amortized cost per push is O(1)
const arr = [];
for (let i = 0; i < 1000; i++) {
  arr.push(i); // Amortized O(1) per push
}

# Python
# Python list.append is amortized O(1)
arr = []
for i in range(1000):
    arr.append(i)  # Amortized O(1)