O(2^n)

2 snippets in Interview Prep

Also written as O(n^2)

DSAInterview Prep

O(n^2) — Quadratic Time

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.