Sliding Window on Arrays in DSA C - Time & Space Complexity

Time Complexity: Sliding Window on Arrays

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when using the sliding window technique on arrays.

How does the number of steps grow as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int maxSumSubarray(int arr[], int n, int k) {
    int max_sum = 0, window_sum = 0;
    for (int i = 0; i < k; i++) {
        window_sum += arr[i];
    }
    max_sum = window_sum;
    for (int i = k; i < n; i++) {
        window_sum += arr[i] - arr[i - k];
        if (window_sum > max_sum) {
            max_sum = window_sum;
        }
    }
    return max_sum;
}
    

This code finds the maximum sum of any subarray of size k using a sliding window.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops that each run over parts of the array.
• How many times: First loop runs k times, second loop runs (n - k) times.

How Execution Grows With Input

The total steps grow roughly in a straight line with the size of the array.

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

Pattern observation: Doubling the array size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the size of the input array.

Common Mistake

[X] Wrong: "The sliding window has nested loops, so it must be O(n²)."

[OK] Correct: The loops run one after another, not inside each other, so total steps add up, not multiply.

Interview Connect

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

Self-Check

"What if we changed the window size k to vary with n, like k = n/2? How would the time complexity change?"