Time and Space Complexity for Coding Interviews: Big-O with Examples
How to work out the Big-O of your own code, the common complexities, and how to use input limits to pick an algorithm.
Coding problems with instant test-case feedback
Write Python, C++, C or JavaScript in your browser and see which hidden tests pass.
Big-O describes how the running time or memory of an algorithm grows as the input grows. In a coding round it decides whether your solution passes the hidden tests or times out, and interviewers almost always ask "what is the complexity of this?" after you code.
1. The rules for calculating Big-O#
- Count how many times the most repeated statement runs, as a function of n.
- Drop constants: 3n + 5 is O(n).
- Keep only the fastest-growing term: n² + n is O(n²).
- Sequential blocks add (O(n) + O(n) = O(n)); nested loops multiply (O(n) inside O(n) = O(n²)).
- Different inputs get different letters: looping over an array of size n and a string of size m is O(n + m), not O(n).
2. Common complexities with examples#
| Complexity | Name | Typical example |
|---|---|---|
| O(1) | Constant | Array access, hash map lookup (average) |
| O(log n) | Logarithmic | Binary search; each step halves the range |
| O(n) | Linear | One pass over an array |
| O(n log n) | Linearithmic | Merge sort, sorting with the standard library |
| O(n²) | Quadratic | Comparing every pair with two nested loops |
| O(2ⁿ) | Exponential | Generating all subsets |
| O(n!) | Factorial | Generating all permutations |
Practise placement aptitude on the real test pattern
TCS NQT, Infosys, Wipro, Accenture and Cognizant style mocks with section-wise analysis.
3. Same problem, three complexities#
Problem: does any pair in the array add up to target? The brute force checks all pairs in O(n²). Sorting plus two pointers is O(n log n). A hash set gives O(n) time at the cost of O(n) extra space.
| 1 | #include <unordered_set> |
| 2 | #include <vector> |
| 3 | |
| 4 | bool hasPair(const std::vector<int>& nums, int target) { // O(n) time, O(n) space |
| 5 | std::unordered_set<int> seen; |
| 6 | for (int x : nums) { |
| 7 | if (seen.count(target - x)) return true; |
| 8 | seen.insert(x); |
| 9 | } |
| 10 | return false; |
| 11 | } |
4. Use the constraints to choose the approach#
Online judges run roughly 10⁸ simple operations per second. Read the input limit before coding and pick a complexity that fits.
| Largest n | Complexity that usually passes |
|---|---|
| n ≤ 10–12 | O(n!) or O(2ⁿ · n) |
| n ≤ 20–25 | O(2ⁿ) |
| n ≤ 500 | O(n³) |
| n ≤ 5,000 | O(n²) |
| n ≤ 10⁶ | O(n log n) or O(n) |
| n ≤ 10¹⁸ | O(log n) or O(1) (maths, binary search) |
Recursion uses stack space: a recursive DFS on a path of length n uses O(n) space even with no extra arrays. Very deep recursion can overflow the stack in C++ and Java.
Test Your Concept Mastery
Verify your retention on: Time and Space Complexity for Coding Interviews: Big-O with Examples
What is the time complexity of a loop where i starts at 1 and doubles each step until it reaches n?
With n up to 10⁵, which approach is safe for a 1-second limit?
Ready for a full proctored assessment?
Take a free aptitude mock on a real company pattern, with a worked solution for every question.
