Why is the time complexity (n*k) instead of ((n-k)*k) for this algorithm?-CodePudding

I am wondering why this brute force approach to a Maximum Sum Subarray of Size K problem is of time complexity nk instead of (n-k)k. Given that we are subtracting K elements from the outer most loop wouldn't the latter be more appropriate? The text solution mentions nk and confuses me slightly.

I have included the short code snippet below!

Thank you

def max_sub_array_of_size_k(k, arr):
    max_sum = 0
    window_sum = 0

    for i in range(len(arr) - k   1):
        window_sum = 0
        for j in range(i, i k):
            window_sum  = arr[j]
        max_sum = max(max_sum, window_sum)
    return max_sum

I haven't actually tried to fix this, I just want to understand.

CodePudding user response：

In the calculation of time complexity, O(n)=O(n-1)=O(n-k) ，both represent the complexity of linear growth, thus O(n-k)✖️O(k) = O(n*k). Of course, this question can be optimized to O(n) time complexity by using the sum of prefixes.

def max_sub_array_of_size_k(k, arr):
    s = [0]
    for i in range(len(arr)):
    # sum[i] = sum of arr[0]   ...   arr[i]
        s.append(s[-1]   arr[i]) 
    
    max_sum = float("-inf")
    for i in range(1, len(s)   1 - k):
        max_sum = max(max_sum, s[i   k - 1] - s[i - 1])
    return max_sum

CodePudding user response：

It's O(k(n-k 1)), actually, and you are right that that is a tighter bound than O(nk).

Big-O gives an upper bound, though, so O(k(n-k 1)) is a subset of O(nk), and saying that the complexity is in O(nk) is also correct.

It's just a question of whether or not the person making the statement about the algorithm's complexity cares about, or cares to communicate, the fact that it can be faster when k is close to n.