Phrase suggestions (did you mean) in Elasticsearch - Time & Space Complexity

Time Complexity: Phrase suggestions (did you mean)

O(n * m)

Understanding Time Complexity

When Elasticsearch suggests alternative phrases for misspelled queries, it runs extra checks to find close matches.

We want to understand how the time needed grows as the number of possible suggestions increases.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch phrase suggestion query.

POST /_search
{
  "suggest": {
    "phrase-suggest": {
      "text": "quikc brown fox",
      "phrase": {
        "field": "content",
        "size": 5
      }
    }
  }
}
    

This query asks Elasticsearch to suggest correct phrases similar to "quikc brown fox" from the "content" field, returning up to 5 suggestions.

Identify Repeating Operations

Look at what repeats when Elasticsearch processes phrase suggestions.

• Primary operation: Checking each candidate phrase against the input phrase to find close matches.
• How many times: For each word in the input phrase, Elasticsearch compares it to many possible terms in the index.

How Execution Grows With Input

As the input phrase gets longer or the index has more terms, the number of comparisons grows.

Input Size (words)	Approx. Operations
3	Thousands of comparisons for each word
10	Many tens of thousands of comparisons
100	Millions of comparisons

Pattern observation: The work grows roughly with the number of words times the number of candidate terms, so it increases quickly as input or index size grows.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of words in the input phrase (n) times the number of candidate terms in the index (m).

Common Mistake

[X] Wrong: "The suggestion time depends only on the input phrase length, not on the index size."

[OK] Correct: Elasticsearch must compare each input word to many terms in the index, so a larger index means more work and longer time.

Interview Connect

Understanding how suggestion queries scale helps you explain search performance and design better user experiences.

Self-Check

"What if we limited the number of candidate terms Elasticsearch checks for each word? How would that affect the time complexity?"