O(n) · SyntaxShelf

O(n) — Linear Time

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!) — 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.

DSAInterview Prep