Module 1 · Complexity and how to think out loud Lesson 4 of 15
Numbers you should know cold
Base cases exist for a reason: for n up to 10, a nested loop is fine; for n up to 100,000 it is not. The n bound in the question tells you which solution is acceptable.
The concept
A few facts save time and make you look prepared. An array index is O(1); searching a sorted array with binary search is O(log n) — about 20 steps for a million items. A hash map lookup is O(1) on average. Sorting is O(n log n). Counting from 1 to 10⁷ in a loop is about a second in Python.
Also worth knowing: 10⁶ operations is comfortable, 10⁸ is not, and that is why an O(n²) solution over 100,000 items cannot pass a time limit no matter how clean it is. When you propose an approach, mention the size of the input it must handle — the constraints are printed in the question and interviewers expect you to read them.
arr[i] O(1)
binary search O(log n) ~20 steps for 1,000,000 items
hash map lookup O(1) average
sort O(n log n)
loop to 10^7 in Python ~1 second
10^6 ops = comfortable. 10^8 ops = too slow. Read the constraints FIRST.Common mistakes
The mistake is proposing a solution the constraints cannot support and discovering it at the end. Read the limits first, sanity-check the complexity against them, then choose the approach. Three seconds of arithmetic saves the round.
Worked example
A question with n up to 10⁵ rules out anything O(n²) before you write it — knowing that saves the interview.
Your practice task
For each of your ten problems, write the largest n that could be accepted with your solution.
Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.
Key takeaway
A few facts save time and make you look prepared.
Keep your place in this course
A free account saves which lessons you have finished and unlocks the certificate. The lesson itself stays free to read.
Create free account or sign inCourse complete
You finished every lesson.
Your certificate is ready, and the projects you built are the proof to attach to an application.
Almost there
15 lessons left of 15
Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.