Nested loops

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.

How to Analyze Time Complexity

DSA · Big-O Notation

syntax

1. Count nested loops
2. Identify recursive branching factor and depth
3. Drop constants and lower-order terms
4. Consider best / average / worst case separately

example

// JavaScript — Analyzing a function
function example(arr) {
  // Loop 1: O(n)
  for (let i = 0; i < arr.length; i++) { /* ... */ }
  // Loop 2 (nested): O(n^2)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { /* ... */ }
  }
}
// Total: O(n) + O(n^2) = O(n^2) — dominated by the larger term

# Python — Same analysis
def example(arr):
    for x in arr:        # O(n)
        pass
    for x in arr:        # O(n^2)
        for y in arr:
            pass
# Total: O(n^2)

output

Always state the dominant term as the final answer.

Note Common trap: a loop inside a loop is not always O(n^2). If the inner loop runs a fixed number of times (say 26 for alphabet), it is O(26n) = O(n). Also watch for hidden loops: string concatenation in a loop is O(n) per concat in many languages, making the total O(n^2).

DSAInterview Prep