CODEWITHSUNDEEP
javatime-complexitybig-onested-loops
dev_ios999
dev_ios999

Reputation: 359

nested loops having linear time complexity?

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) {
        return nums;
    }
    int[] result = new int[n - k + 1];
    LinkedList<Integer> dq = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peek() < i - k + 1) {
            dq.poll();
        }
        while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
            dq.pollLast();
        }
        dq.offer(i);
        if (i - k + 1 >= 0) {
            result[i - k + 1] = nums[dq.peek()];
        }
    }
    return result;
}

As far as i understand the Worst case complexity for this code would be n*k because in the worst case the inner while loop would be executed k times. However the author has said that amortized time Complexity is O(n). How is that ? i don't completely understand ?

Upvotes: 2

Views: 728

Answers (1)

Eran
Eran

Reputation: 393771

Since the inner (while) loop would have a different number of iterations for each iteration of the outer (for) loop, you can't simply bound the number of iterations of that loop by k, since that bound wouldn't be tight enough.

Instead, we can try to compute the total number of operations across all iterations of the inner loop.

The outer loop adds each index exactly once to the queue (in dq.offer(i)).

Each index that was added to the queue, can be removed only once - either by dq.poll() or by dq.pollLast().

Since each iteration of the while loop must remove an element from the queue, all the iterations of the while loop (across all iterations of the outer for loop) are bounded by n (since there cannot be more than n removals). Therefore, all the iterations of the while loop contribute O(n) to the total running time.

Beside the while loop, the other operations inside the outer for loop clearly take constant time, so they cost O(n) time when adding all the iterations of the outer loop.

Hence the total running time is O(n).

Upvotes: 2

Related Questions