Why is this the Time Complexity of this For Loop O(N)?

Issue

Is there a way to understand why the time complexity of the following is O(N), either(or both) from intuition or by proof?

What it does is basically that given the input of an integer array, we are creating the firstSmallLeft array of the same length where firstSmallLeft[i] = the first index where array[index] < array[i] when doing the back scan. (i.e., for index i, it scans from i-1, ... , j until it finds the first smaller element such that array[j] < array[i])

For Example, if input = [3,2,5,6,4,1].
firstSmallLeft would be [-1,-1,1,2,1,-1]

//input int[] array
int[] firstSmallLeft = new int[array.length];
firstSmallLeft[0] = -1;
for(int i = 1; i < array.length; i ++){
    int cur = i -1;
    while (cur >=0 && array[cur] >= array[i]){
        cur = firstSmallLeft[cur];
    }

    firstSmallLeft[i] = cur;
}

Solution

An important insight is that the last entry in firstSmallLeft that received a value (at index i-1) represents the top of a stack, which is implemented as a linked list. An entry in firstSmallLeft represents an input value (as the index where it occurs is the index in the input array) and a link in the linked list (as its value is an index in firstSmallLeft). The bottom element in the stack has a null-link (-1).

In general not all elements in firstSmallLeft are in the represented stack, since some indices are skipped over. An example:

Let's say that the top of the stack is at index 100 (when i is 101), and it has as value 40, and firstSmallLeft[40] is -1, then that means we have a stack with just two elements (array[100] and array[40]), and none of the other indices in firstSmallLeft are included in the current stack. Each one of those once was on the stack, but have since been popped of the stack.

Every time cur = firstSmallLeft[cur]; is executed (in the inner loop), we actually pop an element of the stack (the linked list that starts at cur is one element shorter).

And when we do firstSmallLeft[i] = cur we push array[i] on the stack, making a reference to the part of the stack we wanted to keep.

Now this "virtual" stack is identified, we see the following:

A value is pushed exactly once on the stack, and can only be popped once from the stack, after which it is never visited again.

The overhead of evaluating the while expression once more to find that we need to exit the loop, occurs as many times as the outer loop iterates (i.e. n-1 times)

Therefore the algorithm is O(n).

Answered By - trincot