How to Calculate Time Complexity in an Interview
A practical, step-by-step framework for quickly and accurately determining the Big O time complexity of your code during a high-pressure interview.
The Interview Guarantee
At the end of every whiteboarding or live coding session, the interviewer will ask: "What is the time and space complexity of your solution?" Stumbling here shows a lack of theoretical foundation. You need a fast, reliable framework to calculate Big O on the fly.
Step 1: Identify the Loops
Look purely at the loops in your code.
- No loops (just math/if-statements): O(1)
- One loop going from 0 to N: O(N)
- Two separate loops back-to-back: O(N) + O(N) = O(N)
Step 2: Identify Nesting
Are the loops inside each other?
- Nested loop (Outer runs N times, Inner runs N times): O(N * N) = O(N^2)
- Triple nested loop: O(N^3)
Caution: Check the inner loop's dependency. If the inner loop only runs a constant 5 times, it is O(N * 5), which simplifies to O(N).
Step 3: Identify the Scaling Factor
Does the loop counter add/subtract, or multiply/divide?
i++ori += 2: Linear scaling = O(N)i *= 2ori /= 2: Logarithmic scaling = O(log N)
Step 4: Identify Hidden Complexities
Do not ignore the methods you called!
If you have a single for loop (O(N)), and inside it you call array.sort(), you must calculate the total.
Sorting is O(N log N). Doing it inside a loop makes it O(N * N log N).
Step 5: Drop the Constants
Combine your terms. If your function sorts the array O(N log N), and then loops through it O(N), the raw math is O(N log N + N). Identify the dominant term. As N grows, N log N is far larger than N. Drop the non-dominant N. Final Answer: O(N log N).
The Takeaway
Don't guess the complexity. Trace the loops, multiply the nested ones, add the sequential ones, expose the hidden built-in methods, and drop the smaller terms. Practicing this 5-step framework will make Big O analysis second nature.
Identify all loops. Add sequential loops together. Multiply nested loops. Expose the complexity of built-in methods, and drop non-dominant terms and constants.
It is O(N) + O(N^2). Since N^2 is the dominant term that scales the fastest, the final time complexity is strictly O(N^2).
No, Big O calculates the worst-case scenario. Even if an if-statement breaks the loop on the first try, the algorithm is still classified as O(N).
If a loop iterates over Array A (size N) and a nested loop iterates over Array B (size M), the time complexity is O(N * M), not O(N^2).
Often no. Methods like array.splice(), string.indexOf(), or list.contains() execute hidden O(N) traversal loops under the hood.