The time complexity of the brute force approach is given as O(nk). More specifically, it seems to be (n-k)k = nk - k^2. k always less or equal than n as window size can not be greater than size of array. So is O(nk - k^2) equal to O(nk)? How?
We are calculating the average of an array here. The inner loop runs N times, where we we have to calculate the sum of all the numbers in the array first. So, the time complexity of inner loop is N, which is the size of an array. Further, time complexity of outer loop is k. So, its total time complexity becomes O(nk) not O(nk - k^2).
Not a good answer at all. Absolutely incorrect.
I agree this answer given is not good.
We iterate (n-k+1)(k)=nk-k^2+k times. For instance, if n=k then we iterate n^2-n^2+n=n times. Essentially summing all n elements. Not n^2 times.
The example given says O(nk) and would imply that as k increases our problems runtime increases but this isn’t the case.
That’s a good point. As k increases and approaches n, the time complexity should approach O(k).
For example, if k approaches n, the outer loop iteration count will approach 1, and the inner loop will do most of the leg work, and iterate a k times.
So I think O((n-k)k) makes more sense than O(nk).