Nested loops where both iterate over n.Often a signal to optimize.
Example
// JavaScriptfunctionhasDuplicateBrute(arr){for(let i =0; i < arr.length; i++){for(let j = i +1; j < arr.length; j++){if(arr[i]=== arr[j])returntrue;}}returnfalse;}
# Python
def has_duplicate_brute(arr):for i inrange(len(arr)):for j inrange(i +1,len(arr)):if arr[i]== arr[j]:returnTruereturnFalse
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.
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 functionfunctionexample(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).
Frequently asked questions
How does Interview Prep handle nested loops?
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 "nested loops"?
Besides "O(n^2) - Quadratic Time", this page also shows "How to Analyze Time Complexity".
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.