Term query in Elasticsearch - Time & Space Complexity

Time Complexity: Term query

O(k)

Understanding Time Complexity

When using a term query in Elasticsearch, it's important to know how the search time changes as data grows.

We want to understand how the query's work increases when there are more documents or terms.

Scenario Under Consideration

Analyze the time complexity of the following term query.

GET /my_index/_search
{
  "query": {
    "term": {
      "status": {
        "value": "active"
      }
    }
  }
}
    

This query searches for documents where the field "status" exactly matches "active".

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Checking the inverted index for the term "active" in the "status" field.
• How many times: Once per query, but the number of documents matching can vary.

How Execution Grows With Input

As the number of documents grows, the time to find the term's postings grows too.

Input Size (n)	Approx. Operations
10	Checking a small list of documents for "active"
100	Checking a larger list, more documents to scan
1000	Checking an even bigger list, more matches to process

Pattern observation: The work grows roughly in proportion to how many documents contain the term.

Final Time Complexity

Time Complexity: O(k)

This means the time depends on the number of documents that have the term, not the total documents in the index.

Common Mistake

[X] Wrong: "The term query checks every document in the index every time."

[OK] Correct: Elasticsearch uses an index that directly points to matching documents, so it only checks those with the term.

Interview Connect

Understanding how term queries scale helps you explain search efficiency clearly and confidently in real projects.

Self-Check

What if we changed the term query to a match query? How would the time complexity change?