Time Complexity Interview Questions
What is the output idea of: for i in range(n): for j in range(n): ... What is the time complexity? — spoken sample answer for Indian interviews.
- 5Questions with answers
- 3Difficulty levels
Questions (5)
Browse beginner, intermediate, and advanced questions with answers — hide them when you want to self-test.
What is the output idea of: for i in range(n): for j in range(n): ... What is the time complexity?
Two nested loops that each run n times with O(1) work inside are Theta(n squared). That is the option I would pick, O(n^2) . If the inner loop ran j = 1, 2, 4, ... I would say n log n instead. Always look at how the inner index moves, not only that there are two for-loops.
Complexity of for i in 1..n: for j in 1..i?
Sum 1 to n is n(n+1)/2, O(n^2) . I would not say O(n) from the outer loop only. I write the triangular sum.
Binary search in a balanced BST?
O(log n) if balanced. Skewed is O(n) . I read whether they said worst case or balanced. Iterative space O(1) .
Hash map insert average versus worst?
Average O(1) , worst O(n) on collisions. Java 8 treesify long chains. Oral: I always say average versus worst.
Why n log n beats n^2 for n=10^6?
n^2 is 10^12. n log n is about 2e7. About 1e8 simple ops per second in a contest. That is why we sort then two-pointer.
Practice with AI mock interviews
Run Aptitude mock interviews with AI follow-ups, instant feedback, and analytics on AiLx.
Free to start · No credit card required