Sliding window algorithm in Rest API - Time & Space Complexity

Time Complexity: Sliding window algorithm

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when using the sliding window method in a REST API context.

Specifically, how does the number of operations grow as the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Example: Find max sum of subarray of size k
function maxSumSubarray(arr, k) {
  let maxSum = 0, windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}
    

This code finds the maximum sum of any subarray of size k in the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops that traverse the array.
• How many times: First loop runs k times, second loop runs (n - k) times, where n is array length.

How Execution Grows With Input

As the array size grows, the total steps increase roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with input size, not faster or slower.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "The sliding window always takes more time because it has two loops inside."

[OK] Correct: The loops run one after another, not nested, so total time adds up linearly, not multiplied.

Interview Connect

Understanding sliding window time complexity helps you explain efficient solutions clearly and confidently in interviews.

Self-Check

"What if we changed the window size k to be proportional to n? How would the time complexity change?"