educative.io

Educative

Confusing Comment in Solution and Asymptotic Analysis Issue - Smallest Subarray with Greater Sum

Here is the solution given in Python:

import math

def smallest_subarray_sum(s, arr):
  
  min_length = math.inf

  for window_start in range(0, len(arr)):
    window_sum = 0
    window_end = window_start
    # shrink the window as small as possible until the 'window_sum' is smaller than 's'
    while window_end < len(arr):
      window_sum += arr[window_end]  # add the next element
      if window_sum >=s:
        min_length = min(min_length, window_end - window_start + 1)
        break
      window_end += 1     # Sliding the window
      
  if min_length == math.inf:
    return 0
  return min_length

First, the comment below the for loop says: “# shrink the window as small as possible until the ‘window_sum’ is smaller than ‘s’”. However, we are actually growing the window not shrinking it, and checking if the window_sum is >= s. To me, it seems the worst case runtime is closer to O(n^2) in this solution… for instance take arr = [1, 2, 3, 4, 5] and s = [100], then for each element we iterate over (n-i) elements where i is our current index (going from 0 to 4 in the example) and n is the length of the array (which is 5 in our example).

Your conclusion makes sense. The solution runtime appears to be approximately (n^2)/2 (which is O(n^2)). To confirm it, I counted the inner while loop with the input s=10, arr=[0,0,0,0,0,0,0,0,0,0], and the count was 55. With the array of size 1000, the count was 500500.

1 Like