Why Does My Code Work on Small Test Cases But Fail on Large Ones? (Time Complexity Explained)

You submit your solution. The first few test cases fly by: Accepted. Accepted. Accepted.

Then you hit test case 47 out of 50: Time Limit Exceeded.

You check your code. There's no syntax error. No logical bug. It works—it just doesn't work fast enough.

This is one of the most frustrating experiences for beginners: code that's correct but too slow.

If this sounds familiar, you're experiencing the difference between correctness and efficiency. Your algorithm produces the right answer, but its time complexity makes it impractical for large inputs. In interviews, this distinction can make or break your performance.

This guide will help you understand why your code fails on large test cases, how to diagnose the performance bottleneck, and—most importantly—how to optimize your solution systematically.

TL;DR

• The Problem: Code that"s correct but too slow reveals algorithmic complexity issues—small inputs (n=10) don't stress-test O(n²) or O(2^n) solutions that timeout catastrophically when n=100,000
• Why It Matters: LeetCode allows ~10⁸ operations/second; O(n²) with n=10⁵ means 10¹⁰ operations (timeout), while interviews distinguish between correctness and efficiency—both matter equally
• Core Diagnosis: 3-step analysis: (1) Count loops (k nested loops = O(n^k)), (2) check hidden complexity (list.remove/index/in are O(n)), (3) analyze recursion (naive Fibonacci is O(2^n) without memoization)
• Common Mistake: Missing hidden O(n) operations inside loops—using "x in list" in an O(n) loop creates O(n²) complexity that looks like O(n) at first glance
• What You'll Learn: Constraint-to-complexity mapping (n≤10⁵ needs O(n log n) max), 5 standard optimization patterns (hash maps, memoization, heaps, two pointers), and how to test performance locally before submitting

Why Small Inputs Don't Reveal Performance Issues

Let's start with why your code can appear to work perfectly on small inputs but fail catastrophically on large ones.

The Exponential Growth Problem

Imagine you have an algorithm that checks every pair of elements in an array:

def hasDuplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Time complexity: O(n²)

Performance:

• Input size 10: ~100 comparisons (fast)
• Input size 100: ~10,000 comparisons (still manageable)
• Input size 10,000: ~100,000,000 comparisons (timeout!)

The problem grows quadratically. Small inputs don't stress-test this, so the issue hides until you hit large inputs.

LeetCode's Time Limits

Most LeetCode problems allow approximately 10⁸ operations per second (this varies by language and platform, but it's a useful rule of thumb).

If your algorithm does more than that, you'll see "Time Limit Exceeded."

Common limits:

• If n = 10⁴ (10,000 elements), O(n²) = 10⁸ operations → borderline
• If n = 10⁵ (100,000 elements), O(n²) = 10¹⁰ operations → timeout
• If n = 10⁶, O(n log n) = ~2 × 10⁷ operations → passes

This is why small test cases (n = 10) don't reveal problems that appear when n = 100,000.

Diagnosing the Problem: Identifying Your Time Complexity

Before you can fix the performance issue, you need to understand what's slow.

Step 1: Count the Loops

The easiest way to estimate time complexity is to count nested loops.

Single loop: O(n)

for i in range(n):
    # O(1) operation
    do_something(i)

Two nested loops: O(n²)

for i in range(n):
    for j in range(n):
        # O(1) operation
        do_something(i, j)

Three nested loops: O(n³)

for i in range(n):
    for j in range(n):
        for k in range(n):
            do_something(i, j, k)

General rule: k nested loops = O(n^k)

Step 2: Check Hidden Complexity in Built-In Operations

Be careful: some operations that look O(1) are actually O(n).

Common traps in Python:

• list.remove(x) → O(n)
• list.index(x) → O(n)
• list.pop(0) → O(n) (shifting all elements)
• x in list → O(n)

Example of hidden complexity:

for i in range(n):
    if target in nums:  # This is O(n)
        do_something()

Looks like O(n), actually O(n²) because the in check is O(n) inside an O(n) loop.

Step 3: Analyze Recursive Calls

Recursive functions can have deceptive complexity.

Example: Naive Fibonacci

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Time complexity: O(2^n) — exponential!

Why? Each call spawns two more calls, creating a binary tree of calls with height n.

For n = 50, this is 2^50 ≈ 10¹⁵ operations—utterly impractical.

Common Time Complexity Problems and How to Fix Them

Let's walk through the most common performance bottlenecks and their solutions.

Problem 1: Nested Loops (O(n²) → O(n))

Symptom: Two nested loops, often searching for pairs or checking conditions.

Example: Two Sum (Brute Force)

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Time complexity: O(n²)

Why it fails on large inputs: For n = 100,000, you're doing ~5 billion comparisons.

Solution: Use a Hash Map

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

Time complexity: O(n) — linear!

Key insight: Instead of searching the array for each number (O(n) per search), we store what we've seen in a hash map (O(1) lookup).

Problem 2: Repeated Recalculations (Exponential → Polynomial)

Symptom: Recursive function that recalculates the same subproblem multiple times.

Example: Fibonacci (Exponential)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Time complexity: O(2^n)

Solution: Memoization

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Time complexity: O(n) — each value computed once!

Key insight: Store results of subproblems to avoid redundant computation. This is the foundation of dynamic programming.

Problem 3: Sorting When You Don't Need To (O(n log n) → O(n))

Symptom: Sorting an array when a simpler linear approach exists.

Example: Finding the kth Largest Element

Naive approach:

def findKthLargest(nums, k):
    nums.sort()
    return nums[-k]

Time complexity: O(n log n)

Better approach: Use a heap

import heapq

def findKthLargest(nums, k):
    # Min heap of size k
    return heapq.nlargest(k, nums)[-1]

Time complexity: O(n log k) — much better when k is small!

Or use Quickselect for average O(n):

import random

def findKthLargest(nums, k):
    k = len(nums) - k  # Convert to 0-indexed from the left
    
    def quickselect(left, right):
        pivot = random.randint(left, right)
        nums[pivot], nums[right] = nums[right], nums[pivot]
        
        store_index = left
        for i in range(left, right):
            if nums[i] < nums[right]:
                nums[i], nums[store_index] = nums[store_index], nums[i]
                store_index += 1
        
        nums[store_index], nums[right] = nums[right], nums[store_index]
        
        if store_index == k:
            return nums[store_index]
        elif store_index < k:
            return quickselect(store_index + 1, right)
        else:
            return quickselect(left, store_index - 1)
    
    return quickselect(0, len(nums) - 1)

Time complexity: Average O(n), worst O(n²)

Key insight: Don't sort the entire array if you only need partial information.

Problem 4: Redundant Searches (O(n) per search → O(1) per search)

Symptom: Checking if elements exist by scanning through a list repeatedly.

Example: Finding Intersection of Two Arrays

Naive approach:

def intersection(nums1, nums2):
    result = []
    for num in nums1:
        if num in nums2 and num not in result:  # O(n) + O(m)
            result.append(num)
    return result

Time complexity: O(n × m)

Better approach: Use a hash set

def intersection(nums1, nums2):
    return list(set(nums1) & set(nums2))

Time complexity: O(n + m)

Key insight: Convert to a set for O(1) membership checks.

How to Optimize: A Step-by-Step Framework

When you encounter "Time Limit Exceeded," follow this process:

Step 1: Identify Your Current Complexity

Count loops, check for hidden O(n) operations, analyze recursion.

Ask: "What's my time complexity?"

Step 2: Check the Input Constraints

Look at the problem's constraints (e.g., "1 ≤ n ≤ 10⁵").

This tells you what complexity you can afford:

Example: If n ≤ 10⁵ and you have an O(n²) solution, you need to optimize to O(n log n) or O(n).

Step 3: Identify the Bottleneck

Where is your code spending most of its time?

• Nested loops?
• Repeated searches?
• Redundant calculations?
• Sorting unnecessarily?

Step 4: Apply a Standard Optimization Pattern

Most optimizations fall into a few categories:

Pattern 1: Replace nested loops with hash maps

O(n²) → O(n)

Pattern 2: Use memoization for recursive problems

O(2^n) → O(n) or O(n²)

Pattern 3: Replace linear searches with hash sets

O(n²) → O(n)

Pattern 4: Use heaps instead of sorting

O(n log n) → O(n log k) or O(n)

Pattern 5: Use two pointers instead of nested loops

O(n²) → O(n)

Step 5: Test on Large Inputs Locally

Before resubmitting, test your optimized solution on a large input locally:

import time

# Generate large test case
nums = list(range(100000))
target = 199998

start = time.time()
result = twoSum(nums, target)
end = time.time()

print(f"Result: {result}, Time: {end - start:.4f}s")

If it takes more than 1-2 seconds, you likely still have a complexity issue.

Recognizing When Optimization Is Needed

Here are signals that you need to optimize:

Signal 1: You Have Nested Loops

If you see for i ... for j ..., pause and ask: "Can I eliminate the inner loop with a hash map or two pointers?"

Signal 2: You're Sorting to Solve the Problem

Ask: "Do I really need the array fully sorted, or can I use a heap or partial sorting?"

Signal 3: You're Calling Recursive Functions Without Memoization

If you're solving overlapping subproblems (like Fibonacci), add memoization.

Signal 4: You're Searching the Same Structure Repeatedly

If you're checking if x in list inside a loop, convert to a set.

Common Mistakes That Cause Timeouts

Mistake 1: Using the Wrong Data Structure

Using a list when you should use a set or hash map.

Example:

# Slow: O(n) per check
for item in items:
    if item in my_list:
        do_something()

# Fast: O(1) per check
my_set = set(my_list)
for item in items:
    if item in my_set:
        do_something()

Mistake 2: Not Recognizing Hidden Complexity

Using .index(), .remove(), or in on lists without realizing they're O(n).

Mistake 3: Unnecessary Sorting

Sorting when you only need partial information (like the maximum or kth largest).

Mistake 4: Ignoring Space-Time Tradeoffs

Sometimes using O(n) extra space (hash map, memoization) reduces time from O(n²) to O(n). That's almost always worth it.

When to Ask for Help

If you've identified your time complexity, checked the constraints, and tried standard optimizations but still can't find a faster approach, it might be time to seek hints.

Tools like LeetCopilot can provide targeted suggestions about which optimization pattern to try (memoization, hash maps, two pointers) without giving away the full solution—helping you learn the optimization technique yourself.

FAQ

Why does my O(n²) solution pass some O(n²) problems but not others?

It depends on the constant factors and the exact constraint. If n ≤ 1,000, O(n²) might pass. If n ≤ 100,000, it won't. Always check the constraints.

How can I tell if my solution is fast enough before submitting?

Test it locally on a large input. If it takes more than 1-2 seconds for the max constraint, it's likely too slow.

Is O(n log n) always better than O(n²)?

For large n, yes. But for very small n (< 10), the constant factors and simplicity might make O(n²) acceptable.

What if I can't think of a faster algorithm?

Start by asking: "What operation am I repeating? Can I store results instead of recalculating?" Often, the answer is memoization or using a hash map.

Should I always optimize for the best possible time complexity?

In interviews, get a working solution first, then optimize. A correct O(n²) solution is better than a broken O(n) attempt.

Conclusion

When your code works on small test cases but fails on large ones, it's not a bug—it's a time complexity issue.

The fix:

1. Identify your current complexity (count loops, check hidden operations)
2. Check the constraints to know what complexity you need
3. Find the bottleneck (nested loops, repeated calculations, unnecessary sorting)
4. Apply standard patterns (hash maps, memoization, heaps, two pointers)
5. Test on large inputs before resubmitting

Mastering time complexity isn't about memorizing Big O notation—it's about recognizing when your solution is doing redundant work and knowing the standard techniques to eliminate it.

With practice and the right coding interview guide approach, you'll start seeing these optimization opportunities instantly, transforming "Time Limit Exceeded" from a frustrating dead-end into a solvable puzzle.