Correlation ID for matching replies in RabbitMQ - Time & Space Complexity

Time Complexity: Correlation ID for matching replies

O(n)

Understanding Time Complexity

When using correlation IDs in RabbitMQ, we want to see how the time to find the matching reply changes as more messages are processed.

We ask: How does the effort to match replies grow with the number of outstanding requests?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for handling replies with correlation IDs
onReplyReceived(reply) {
  for (let request of pendingRequests) {
    if (request.correlationId === reply.correlationId) {
      processReply(reply);
      // remove request from pendingRequests
      break;
    }
  }
}

This code searches through pending requests to find the one matching the reply's correlation ID.

Identify Repeating Operations

• Primary operation: Looping through the list of pending requests to find a matching correlation ID.
• How many times: Once per reply received, scanning up to all pending requests.

How Execution Grows With Input

As the number of pending requests grows, the search to find a matching reply takes longer.

Input Size (n)	Approx. Operations
10	Up to 10 comparisons
100	Up to 100 comparisons
1000	Up to 1000 comparisons

Pattern observation: The time to find a match grows linearly as the number of pending requests increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the matching reply grows directly with the number of pending requests.

Common Mistake

[X] Wrong: "Matching replies with correlation IDs is always fast regardless of how many requests are pending."

[OK] Correct: If you search through a list without a fast lookup, the time grows as the list grows, making matching slower with more requests.

Interview Connect

Understanding how correlation ID matching scales helps you design efficient messaging systems and shows you can reason about performance in real-world scenarios.

Self-Check

What if we used a hash map to store pending requests by correlation ID? How would the time complexity change?