Bidirectional relationships in GraphQL - Time & Space Complexity

Time Complexity: Bidirectional relationships

O(n * m)

Understanding Time Complexity

When working with bidirectional relationships in GraphQL, it's important to understand how the time to fetch data grows as the related data grows.

We want to know how the number of operations changes when we query connected data in both directions.

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query fetching bidirectional relationships.

query {
  authors {
    id
    name
    books {
      id
      title
      author {
        id
        name
      }
    }
  }
}
    

This query fetches authors, their books, and for each book, the author again, showing a bidirectional link.

Identify Repeating Operations

Look for repeated data fetching steps in the query.

• Primary operation: Loop over all authors, then for each author loop over their books, then for each book fetch the author again.
• How many times: The author list is traversed once, books are traversed for each author, and author info is fetched again for each book.

How Execution Grows With Input

As the number of authors and books grows, the operations increase accordingly.

Input Size (n authors, m books per author)	Approx. Operations
10 authors, 5 books each	10 + (10 * 5) + (10 * 5) = 10 + 50 + 50 = 110
100 authors, 5 books each	100 + (100 * 5) + (100 * 5) = 100 + 500 + 500 = 1100
1000 authors, 5 books each	1000 + (1000 * 5) + (1000 * 5) = 1000 + 5000 + 5000 = 11000

Pattern observation: The operations grow roughly in proportion to the number of authors times the number of books per author.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of authors multiplied by the number of books each author has.

Common Mistake

[X] Wrong: "Fetching the author inside each book doesn't add extra cost because it's the same author."

[OK] Correct: Even if it's the same author, the query repeats fetching author data for every book, so the operations add up with each book.

Interview Connect

Understanding how bidirectional data fetching scales helps you design efficient queries and avoid slow responses in real apps.

Self-Check

What if we removed fetching the author inside each book? How would the time complexity change?