PPractick

The problem

Your team's code review bot flags any function it thinks might be too slow, but it can't explain why. You're asked to go through six small loop shapes that keep appearing in the codebase, work out the Big-O time complexity of each, and back your answers up by counting how many times the loop body actually runs. The goal is to be able to glance at any piece of code, name its complexity, and use the problem's constraints to decide whether it will run in time. That's a skill every interviewer checks after you write a solution.

Example: a loop that halves n each time, like for (i = n; i > 0; i /= 2), runs about log₂(n) times. For n = 1000 that's only 10 iterations.

Function signature

long long countLinear(long long n);      // for i < n                          -> O(n)
long long countNested(long long n);      // for i < n, for j < n              -> O(n^2)
long long countTriangular(long long n);  // for i < n, for j < i              -> O(n^2)
long long countHalving(long long n);     // for i = n; i > 0; i /= 2          -> O(log n)
long long countSqrt(long long n);        // for i = 1; i * i <= n; i++        -> O(sqrt n)
long long fibCalls(int n);               // naive recursive Fibonacci         -> O(2^n)

Test cases

Input n	Linear	Nested	Triangular	Halving	Sqrt
16	16	256	120	5	4
1000	1000	1000000	499500	10	31

Input n	fibCalls(n)	Explanation
10	177	Calls roughly double as n grows
20	21891
30	2692537	About 2.7 million calls for n = 30

(Confirm: the functions return how many times the innermost statement runs, so the counts can be compared with the predicted Big-O.)

How interviewers phrase it

• After any solution: "What's the time and space complexity of your code?"
• "What's the complexity of this snippet?" followed by nested loops, a halving loop, or a recursive function.
• "N is up to 10^5. Will your O(N²) solution pass?"
• Theory: "What does Big-O mean? What's the difference between O, Θ and Ω?"

Clarifying questions to ask

1. Do you want the worst case, the average case, or both?
2. Should space complexity include the input, or only the extra memory the algorithm uses?
3. What are the constraints on N? (That decides which complexities are acceptable.)
4. Are there several input sizes, like N and M, that the complexity should be expressed in?

Follow-ups to expect

1. "Why do we drop constants and lower-order terms?"
2. "How many operations fit in one second?"
3. "The inner loop runs j < i, not j < n. Isn't that faster?"
4. "Why is halving O(log n)?"
5. "What's the space complexity of recursion?"
6. "Big-O vs Θ vs Ω?"

Related questions

• Input Output Easy
• Cpp Basics Easy
• If ElseIf Easy
• Switch Case Easy
• What are arrays, strings? Easy
• For loops Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in