Work grows directly with input size.One pass through the data.
Example
// JavaScriptfunctionfindMax(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.
Generating all permutations of n items.Grows astronomically fast.
Example
// JavaScriptfunctionpermutations(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 ofpermutations(rest)){
result.push([arr[i],...perm]);}}return result;}
# Python
def get_permutations(arr):iflen(arr)<=1:return[arr[:]]
result =[]for i inrange(len(arr)):
rest = arr[:i]+ arr[i+1:]for perm inget_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 O(n)?
Interview Prep covers this with 2 copy-ready snippets on this page. The "O(n) - Linear Time" snippet in Interview Prep uses `Work grows directly with input size. One pass through the data.`.
Which code does the Interview Prep example use?
The "O(n) - Linear Time" snippet uses `Work grows directly with input size. One pass through the data.`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "O(n)"?
Besides "O(n) - Linear Time", this page also shows "O(n!) - Factorial Time".
Is there anything to watch out for?
Yes. For "O(n) - Linear Time": 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.