Revision and Interview Questions

Cheat sheet

Goal: describe how work and memory grow with input size n. Cases: best, worst (most common, a guarantee), average. Notation: O upper bound, Ω lower bound, Θ tight bound, o and ω strict; drop constants and lower-order terms; log base irrelevant; keep separate variables (O(n + m), O(n · m)). Growth order: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!. Loops: single O(n); nested O(n²); triangular n(n−1)/2 = O(n²); halving or doubling O(log n); i·i ≤ n gives O(√n); harmonic O(n log n); two pointers and sliding windows O(n) by total movement. Recursion: recurrences; T(n−1)+1 = O(n); T(n/2)+1 = O(log n); 2T(n/2)+n = O(n log n); naive Fibonacci exponential; master theorem compares f(n) with n^(log_b a). Space: auxiliary vs input; recursion depth counts; in-place = O(1) extra. Data structures: array index O(1), insert middle O(n), dynamic append amortised O(1); hash O(1) average; balanced BST O(log n); heap O(log n) push/pop, O(1) peek. Sorting: comparison lower bound Ω(n log n); counting/radix beat it for bounded integers. Classes: P, NP, NP-complete; pseudo-polynomial DP. Practice: constraints guide complexity; measure real performance.

Common interview questions

Answer each with the complexity and a one-line justification.

1. What is the time and space complexity of binary search (iterative and recursive)?
2. Why is appending to a Python list or Java ArrayList amortised O(1)?
3. What is the complexity of: for i in 1..n: for j = i; j <= n; j += i?
4. Solve T(n) = 2T(n/2) + n and T(n) = T(n/2) + n.
5. Why is naive recursive Fibonacci exponential, and how does memoisation fix it?
6. What is the difference between O, Omega and Theta?
7. Why can no comparison sort beat Omega(n log n) in the worst case?
8. How would you make a duplicate check faster than O(n^2)? What does it cost?
9. What is the space complexity of recursive DFS on a graph with V vertices?
10. Given n <= 10^5, which complexities are acceptable and why?

Always state time and space

End every solution with a sentence such as "O(n log n) time for the sort and O(n) extra space for the map". Interviewers expect it, and it often reveals a cheaper alternative.

त्वरित जाँच: What is the solution of T(n) = T(n/2) + n?

• Θ(log n)
• Θ(n log n)
• Θ(n²)
• Θ(n)