Big o

7 snippets in Interview Prep

DSAInterview Prep

O(1) — Constant Time

syntax

Operations that execute in the same time regardless of input size.

example

// 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

output

Time: O(1) | Space: O(1)

Note Hash map lookups are O(1) average but O(n) worst case due to collisions. Array index access is always O(1). Interviewers love asking: 'Is this truly constant?' — know the difference between average and worst case.

O(log n) — Logarithmic Time

DSA · Big-O Notation

syntax

Each step halves the remaining work. Classic sign: dividing the problem space in two.

example

// 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

output

Time: O(log n) | Space: O(1)

Note Balanced BST operations are O(log n). Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow. If you see 'sorted array' in a problem, think binary search immediately.

O(n) — Linear Time

DSA · Big-O Notation

syntax

Work grows directly with input size. One pass through the data.

example

// 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

output

Time: O(n) | Space: O(1)

Note Single loop over n elements is O(n). Two separate loops (not nested) is still O(n) — O(2n) simplifies to O(n). Interviewers want you to drop constants and lower-order terms.

O(n log n) — Linearithmic Time

DSA · Big-O Notation

syntax

Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work per level.

example

// 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)

output

Time: O(n log n) | Space: O(n) for merge sort, O(log n) for quicksort avg

Note O(n log n) is the theoretical lower bound for comparison-based sorting. If an interviewer asks you to do better, the input must have special structure (e.g., bounded integers for counting sort). Heap operations on n elements also yield O(n log n).

O(n^2) — Quadratic Time

DSA · Big-O Notation

syntax

Nested loops where both iterate over n. Often a signal to optimize.

example

// 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

output

Time: O(n^2) | Space: O(1)

Note Bubble sort, selection sort, and insertion sort are all O(n^2). If your brute force is O(n^2), try using a hash map or sorting to bring it down to O(n) or O(n log n). Interviewers often want you to identify the brute force first, then optimize.

O(2^n) — Exponential Time

DSA · Big-O Notation

syntax

Each element doubles the work. Common in recursive solutions without memoization.

example

// 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)

output

Time: O(2^n) without memo | O(n) with memo | Space: O(n)

Note Generating all subsets of a set is O(2^n). This is a red flag in interviews — if your solution is exponential, look for overlapping subproblems (DP) or pruning (backtracking). Always mention that memoization brings it down.

O(n!) — Factorial Time

DSA · Big-O Notation

syntax

Generating all permutations of n items. Grows astronomically fast.

example

// 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

output

Time: O(n!) | Space: O(n!) to store all permutations

Note 10! = 3,628,800 and 20! is over 2 quintillion. If n > ~10-12, factorial algorithms won't finish in time. The traveling salesman brute force is O(n!). Interviewers accept factorial only when generating all permutations is required.