B-TIER resource
Time complexity patterns — ten loop shapes to recognize in interviews
100k ft — What is this?
Time complexity patterns — ten loop shapes to recognize in interviews
50k ft — Why care?
Cheat sheet mapping code shapes to Big-O: hash lookup O(1), halving loop O(log n), single and sequential loops O(n) and O(n+m), loop plus binary search and divide-and-conquer O(n log n), nested and triangular loops O(n²), branching recursion exponential, permutations O(n!).
10k ft — Key takeaways
• Recognize the loop shape to read off complexity fast
• Triangular loops are still O(n²)
5k ft — Tools & techniques
(no tools tagged)
code generation, complexity analysis
1k ft — Deep-dive / try it
10 Must-Know Time Complexity Patterns for Interviews
1. 𝐇𝐚𝐬𝐡 𝐋𝐨𝐨𝐤𝐮𝐩 - 𝐎(1) 𝐚𝐯𝐞𝐫𝐚𝐠𝐞
A lookup usually takes constant time, regardless of input size. In the worst case, it can degrade to O(n).
2. 𝐇𝐚𝐥𝐯𝐢𝐧𝐠 𝐋𝐨𝐨𝐩 - 𝐎(𝐥𝐨𝐠 𝐧)
The input size is divided by a constant factor in every step, such as in binary search.
3. 𝐒𝐢𝐧𝐠𝐥𝐞 𝐋𝐨𝐨𝐩 - 𝐎(𝐧)
Each element is processed once.
4. 𝐒𝐞𝐪𝐮𝐞𝐧𝐭𝐢𝐚𝐥 𝐋𝐨𝐨𝐩𝐬 - 𝐎(𝐧 + 𝐦)
You iterate over two separate inputs one after another, not with one loop nested inside the other.
5. 𝐋𝐨𝐨𝐩 + 𝐁𝐢𝐧𝐚𝐫𝐲 𝐒𝐞𝐚𝐫𝐜𝐡 - 𝐎(𝐧 𝐥𝐨𝐠 𝐧)
A loop runs n times, and each iteration performs O(log n) work.
6. 𝐃𝐢𝐯𝐢𝐝𝐞 & 𝐂𝐨𝐧𝐪𝐮𝐞𝐫 - 𝐎(𝐧 𝐥𝐨𝐠 𝐧)
The problem is divided across roughly log n levels, with O(n) total work at each level. Merge sort is a common example.
7. 𝐍𝐞𝐬𝐭𝐞𝐝 𝐋𝐨𝐨𝐩𝐬 - 𝐎(𝐧²)
For every element, you ite…
Transcript excerpt
(no speech detected)