Cache invalidation strategies in Rest API - Time & Space Complexity

Time Complexity: Cache invalidation strategies

O(n)

Understanding Time Complexity

When using cache invalidation strategies in REST APIs, it's important to understand how the time to update or clear cache changes as the data grows.

We want to know how the cost of invalidating cache scales with the number of cached items or requests.

Scenario Under Consideration

Analyze the time complexity of this cache invalidation example.

// Simple cache invalidation by key
function invalidateCache(keys) {
  keys.forEach(key => {
    cache.delete(key);
  });
}

// keys is an array of cache keys to remove

This code removes cached items one by one by their keys.

Identify Repeating Operations

Look at what repeats in this code.

• Primary operation: Looping over each cache key to delete.
• How many times: Once for each key in the input list.

How Execution Grows With Input

As the number of keys to invalidate grows, the time to remove them grows too.

Input Size (n)	Approx. Operations
10	10 deletions
100	100 deletions
1000	1000 deletions

Pattern observation: The time grows directly with the number of keys to invalidate.

Final Time Complexity

Time Complexity: O(n)

This means the time to invalidate cache grows linearly with the number of keys you want to remove.

Common Mistake

[X] Wrong: "Invalidating cache keys is always instant, no matter how many keys there are."

[OK] Correct: Each key removal takes time, so more keys mean more work and longer time.

Interview Connect

Understanding how cache invalidation scales helps you design efficient APIs and shows you can think about performance in real systems.

Self-Check

"What if the cache invalidation used a pattern to delete keys in bulk instead of one by one? How would the time complexity change?"