SyntaxShelf

Big o

7 snippets in Interview Prep

DSAInterview Prep

O(1) - Constant Time

DSA · Big-O Notation
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.

Frequently asked questions

How does Interview Prep handle big o?
Interview Prep covers this with 7 copy-ready snippets on this page. The "O(1) - Constant Time" snippet in Interview Prep uses `Operations that execute in the same time regardless of input size.`.
Which code does the Interview Prep example use?
The "O(1) - Constant Time" snippet uses `Operations that execute in the same time regardless of input size.`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "big o"?
Besides "O(1) - Constant Time", this page also shows "O(log n) - Logarithmic Time", "O(n) - Linear Time", "O(n log n) - Linearithmic Time", "O(n^2) - Quadratic Time".
Is there anything to watch out for?
Yes. For "O(1) - Constant Time": 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.

Browse all tasks by intent