SyntaxShelf

O(2^n)

2 snippets in Interview Prep

Also written as O(n^2)

DSAInterview Prep

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.

Frequently asked questions

How does Interview Prep handle O(2^n)?
Interview Prep covers this with 2 copy-ready snippets on this page. The "O(n^2) - Quadratic Time" snippet in Interview Prep uses `Nested loops where both iterate over n. Often a signal to optimize.`.
Which code does the Interview Prep example use?
The "O(n^2) - Quadratic Time" snippet uses `Nested loops where both iterate over n. Often a signal to optimize.`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "O(2^n)"?
Besides "O(n^2) - Quadratic Time", this page also shows "O(2^n) - Exponential Time".
Is there anything to watch out for?
Yes. For "O(n^2) - Quadratic Time": 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.

Browse all tasks by intent