One of the most important ideas in computer science is something called Big O notation. It’s a way to measure how efficient an algorithm (or a computer program) is, by looking at how much time or memory it needs as the amount of data it processes increases. Think of it like a scorecard that tells you how well a program can handle bigger and bigger tasks. Big O helps us understand how a program’s performance changes when it has to deal with more data, so we can figure out which programs are faster or more efficient.

Reference the diagram and table below:

In this article, we will explore Big O notation through the lens of a social media application. We will compare the performance differences between REST API and GraphQL API using Big O notation.

REST API Requests and Time Impact

In the realm of RESTful APIs, the type of HTTP request made—be it GET, POST, PUT, or DELETE—significantly influences the time and resources required for operations.

This are our social media API endpoints:

1. POST /posts: Create a new post.
2. GET /posts: Retrieve a list of posts.
3. GET /posts/{id}: Retrieve a specific post.
4. POST /posts/{id}/comments:Add a comment to a post.
5. GET /posts/{id}/comments: Get all comments for a specific post.
6. POST /comments/{id}/replies: Add a reply to a comment.
7. GET /comments/{id}/replies: Get all replies for a specific comment.

Each request type corresponds to specific actions that can either streamline or complicate communication between clients and servers. Understanding these impacts is crucial for optimizing performance and enhancing user experience.

1. POST /posts (Add a post)

Action: This adds a new post.
Impact: The time taken depends on the size of the post data and the server's processing time. If additional requests are made to retrieve updated data (e.g., fetching the latest list of posts or comments), this can introduce additional latency and increase overall response time.
Big-O Complexity:The operation to create a single post is O(1) since it involves a fixed action regardless of the dataset size. However, additional network requests to fetch updated data contribute to overall overhead.

2. GET /posts (Retrieve a list of posts)

Action: This request fetches a collection of resources, specifically a list of posts.
Impact: The time taken for this operation increases with the number of posts. As the server compiles the list, it may also need to retrieve related resources, such as comments associated with each post. This can lead to multiple HTTP requests, particularly if comments are fetched separately for each post.
Big-O Complexity: O(n), where n represents the number of posts. If related resources like comments are included in the response, the complexity further escalates due to additional requests.

3. GET /posts/{id} (Retrieve a specific post)

Action: This request retrieves a single resource identified by its unique ID.
Impact: The time complexity is linear for fetching the post itself; however, if related resources (like comments) are required, additional requests will be necessary, increasing overall latency.
Big-O Complexity: O(1) for retrieving the post alone, but additional time is needed for each subsequent request for related resources.

4. POST /posts/{id}/comments (Add a comment to a post)

Action: This modifies an existing resource by adding a new comment.
Impact: The time taken depends on the size of the comment data and how long the server takes to process this update. If followed by another request to fetch updated data (such as the new list of comments), this can introduce further latency.
Big-O Complexity: O(1) for creating a single comment, but network overhead increases due to the necessity of confirming changes.

5. GET /posts/{id}/comments (Get all comments for a post)

Action: This retrieves all comments associated with a specific post.
Impact: This operation requires an additional network round-trip for every post request made, contributing to increased latency.
Big-O Complexity: O(m), where m is the number of comments linked to that particular post.

6. POST /comments/{id}/replies (Add a reply to a comment)

Action: This modifies an existing resource by adding a reply to a specific comment.
Impact: Similar to adding comments, this action incurs additional network overhead when fetching updated data afterward.
Big-O Complexity: O(1), but again impacted by subsequent requests to retrieve replies.

7. GET /comments/{id}/replies (Get all replies for a specific comment)

Action: This retrieves all replies associated with a specific comment.
Impact: Each request adds latency due to additional HTTP requests needed, especially if there are nested replies that require further fetching.
Big-O Complexity: O(p), where p is the number of replies linked to that particular comment.

GraphQL and Time Impact

GraphQL improves on the limitations of REST APIs by allowing users to combine multiple data requests into one single query. Instead of needing to make several requests to different URLs to get the information you want, GraphQL lets you specify exactly what data you need all at once. This means less waiting time because it cuts down on the number of times your computer has to communicate with the server, making everything faster and more efficient.

1. Single Request for Multiple Resources:

• GraphQL improves on REST APIs by allowing users to combine multiple data requests into a single query. Instead of making several requests to different URLs, GraphQL lets you specify exactly what data you need all at once, reducing wait times and making the process faster and more efficient.

• Big-O O(1) : In GraphQL, this operation simplifies complexity to O(1) for a single network round-trip, allowing nested data to be fetched in one request. This optimizes overall time since the client specifies exactly what it needs.

2. Narrower Data Fetching:

With GraphQL, clients avoid over-fetching and under-fetching. The client only requests the exact fields necessary, leading to smaller response sizes and faster processing times.
Big-O: O(n)where n is the number of fields requested, but since the request is optimized, the network and processing time is generally faster.

Big-O and Performance in GraphQL

• Client-side Efficiency: With GraphQL, the client clearly states exactly what data it needs, which helps avoid the delays of making multiple requests. This results in better performance when handling large sets of related data, achieving O(n) efficiency. Instead of the server processing many requests as in REST, it only needs to handle one, minimizing unnecessary work.

• Server-side Efficiency: In a REST API, the server often fetches data from different sources (like posts, comments, and replies) one at a time, which can take longer (O(n + m + p)). With GraphQL, all the data is fetched in a single request, making it faster and more efficient.

• Nested Resources: One of the key benefits of GraphQL is its ability to efficiently manage nested resources. Clients can retrieve data in a hierarchical structure with just one query, rather than needing multiple requests as in REST.

Example: Comparing Time Complexity in REST vs. GraphQL

Consider a scenario where we want to fetch a post, its comments, and the replies to each comment:

REST API:

• Step 1: Step 1: GET /posts/{id} (O(1))
• Step 2: GET /posts/{id}/comments (O(m))
• Step 3: For each comment, GET /comments/{id}/replies (O(p))

Total Time Complexity: O(1 + m + p) — Multiple round-trips increase latency.

GraphQL:

Query:

post(id: 1) {
  id
  title
  comments {
    id
    comment
    replies {
      id
      reply
    }
  }
}

Time Complexity: O(1) — All data is fetched in a single query, reducing the overall time.

Conclusion:

• REST API leads to increased latency due to multiple requests and their associated overhead.

• GraphQL resolves this by consolidating requests into a single query, optimizing the time complexity and reducing the number of network round-trips, leading to faster responses and better overall performance, especially when handling nested data or large sets of resources.