Time Complexity Practice Problems

Working Through Time Complexity Practice Problems

Most people approach time complexity practice problems the wrong way. They pick a random LeetCode question, stare at it for twenty minutes, then immediately check the editorial when they can't solve it. That's not how you get better at this. You need a structured practice routine that actually builds intuition instead of just burning through easy questions. The usual suspects are LeetCode, Codeforces, AtCoder, and HackerRank. But honestly, the platform barely matters. What matters is how you sequence your practice. Start with problems that isolate a single concept — amortized analysis, the master theorem, recursion trees — rather than jumping into mixed bag contests where everything is lumped together. Codeforces Div 2 A and B problems on arrays are fine warmups, but they rarely force you to think about big-O meaningfully. For actual time complexity work, you want problems that reward algorithmic choice, not just implementation speed. I keep a personal repo on GitHub where I sort problems by the specific complexity concept they target. It takes about two hours to set up if you're organized about it, but it saves you from randomly grinding problems that don't actually teach you anything new. The repo isn't public — I'd rather not advertise it — but the structure is simple enough that you can rebuild it yourself.

Here's the practical method I use before writing a single line of code. First, I read the problem and estimate the brute force solution's time complexity. That gives me a baseline. Then I ask myself what operation dominates that baseline — nested loops, redundant recalculations, unnecessary sorting — and which optimization technique maps to that bottleneck. If it's overlapping subproblems, I'm looking at DP or memoization. If it's redundant computation on sorted data, I'm thinking two pointers or binary search. If it's repeated queries over a range, I'm considering prefix sums or segment trees. This mental mapping step usually takes three to five minutes and prevents me from stumbling into an O(n²) solution that would TLE on a medium input size.

The Analysis Phase Is Where People Fail

Writing the correct algorithm is the easy part for most people who already know the patterns. The hard part is proving — to yourself, not to a judge — what the time complexity actually is. I see this constantly in intern interviews. Someone implements a merge sort and claims O(n log n), but when asked to walk through why the recursion depth is log n and why each level does O(n) work, they hesitate. They know the answer but they don't own the reasoning. When you're practicing, always write out your complexity analysis before submitting. Don't just assume. If your solution has a loop inside a recursive call, that doesn't automatically make it O(n²). It might be O(n log n) if the recursion halves the input each time, or O(n) if the recursive calls only happen once. You need to actually trace the recurrence relation and solve it. The master theorem covers the standard cases, but a lot of real interview problems have recurrences that don't fit neatly into cases 1, 2, or 3. In those situations, the iteration method — unrolling the recurrence step by step — is usually faster and less error-prone than trying to force-fit it to the master theorem. One thing I learned the hard way: when analyzing problems with multiple phases, don't add the complexities naively. If you sort an array in O(n log n) and then do a linear scan in O(n), the total is O(n log n) because that's the dominant term. But if you then do another sort after filtering down to k elements, it's O(n log n + k log k), which is still O(n log n) in the worst case. The mistake people make is treating each phase as equally important rather than identifying the bottleneck. This is especially relevant for Time Complexity Practice Problems where multiple operations stack up.

Common Pitfalls in Complexity Analysis

The most frequent error I see is confusing worst case with average case. A quicksort implementation might have an average case of O(n log n), but if the interviewer specifically asks about worst case, the answer is O(n²). Some problems explicitly state constraints that avoid the worst case — like guaranteeing random input or limiting the input range — but you should never assume that unless it's stated. Always clarify with the interviewer or stick to worst case analysis by default. Another trap is ignoring the constant factors in practice. Big-O notation abstracts them away, but in real coding interviews, a solution that's theoretically O(n) but makes three passes over the data will sometimes lose to a clever O(n log n) solution that does everything in one pass on a small dataset. This is why understanding the actual constraints matters. If n is at most 1000, O(n²) runs in about a millisecond on modern hardware. If n is 10, that same O(n²) hits 10¹ operations and will definitely time out. The threshold where O(n²) becomes unacceptable varies by problem, but 10 to 10 operations per second is a reasonable ballpark for most online judges. Space complexity gets less attention than it deserves, and that's a mistake. Some interviewers will penalize you for an O(n) space solution when an O(1) space solution exists. In-place sorting, the two-pointer technique with modified input, or reusing the input array are all fair game unless the problem explicitly says not to modify the input. Always ask about space constraints early. I once lost a coding round because I used a hash map for frequency counting when a sorted array approach would have used O(1) extra space. The time complexity was identical, but the space difference was the deciding factor.

A Practical Practice Routine

Here's what I actually recommend if you're serious about this. Spend two weeks purely on problems that target one complexity class at a time. Week one: O(n) and O(n log n) problems. Week two: O(n²) and exponential problems where you need to optimize down. After each session, write a one-line summary of the pattern and the recurrence or analysis method you used. This forces you to consolidate what you learned instead of just completing another problem and moving on. Then switch to timed conditions. Give yourself twenty minutes per medium-difficulty problem. If you can't solve it in that window, you don't have a pattern recognition problem — you have a fundamental gap. Go back to the concept and practice more targeted problems. This is uncomfortable but necessary. Most people avoid the gap-filling stage because it's less fun than solving new problems, which is exactly why they plateau. For Space Complexity Practice Problems, the same discipline applies. Track your auxiliary space separately from your input space. When you modify the input array in place, that's O(1) auxiliary space, not O(1) total space. Distinguish between the two and be precise about it. Interviewers who care about space complexity will notice the difference.

My Specific Struggle with a Recursion Tree Problem

A couple years ago I was working through a problem that involved a recursive function splitting an array into thirds instead of halves at each step, with a loop doing O(n) work at every level. My initial instinct was to apply the master theorem blindly, but the recurrence was T(n) = 3T(n/3) + O(n), which actually falls into case 2 and gives O(n log n). The trap was that I immediately second-guessed myself because I'd seen similar problems before where the answer was O(n²), and my pattern-matching brain wanted to force it into that category. I caught the error by drawing out the recursion tree manually — three levels deep, each level summing to n, depth of logn — which confirmed the O(n log n) result. The lesson was that pattern recognition is useful until it's wrong, and manual verification is the only safeguard against confident mistakes. This kind of error is more common than you'd think, especially under interview pressure. The workaround isn't to memorize more problems. It's to develop the habit of always sketching the recursion tree or unrolling the recurrence for any recursive solution you propose, even when it seems straightforward. That five-minute check catches errors that cost you the entire interview.

What This Approach Doesn't Fix

Time complexity practice problems won't make you a better systems programmer. Understanding asymptotic analysis doesn't teach you about cache locality, branch prediction, or memory alignment. If your O(n log n) solution is thrashing the CPU cache because of pointer chasing through linked lists, a well-written O(n²) solution using contiguous arrays might actually be faster for realistic input sizes. This is a real phenomenon, not a theoretical edge case. I've seen it in production code where a supposedly optimal algorithm was slower than a simpler alternative because the optimal one had poor spatial locality. Also, big-O analysis assumes the input size grows arbitrarily large. In practice, many problems have constrained input sizes where the asymptotic behavior is irrelevant. An O(n²) solution with n 500 is perfectly acceptable and often simpler to implement and debug than an O(n log n) alternative. Don't prematurely optimize. Write the simplest correct solution first, measure it against the constraints, and only reach for the complex algorithm if the simple one doesn't fit the time budget. If you're preparing for competitive programming specifically, the practice volume needs to be much higher than I described above — probably 300 to 500 problems minimum before you feel comfortable. For technical interviews, a focused set of 80 to 120 problems across the major patterns is sufficient if you analyze each one thoroughly. Quality of analysis matters more than quantity of problems attempted.