Want to know the time complexity inner for loop which is partially iterating the array

Question

Question: Find out next increasing value of each element in this below array.

int[] array = { 5, 2, 7, 10, 4, 12}

e.g)
5's nextIncreasingValue: 7
2's nextIncreasingValue: 7
7's nextIncreasingValue: 10
...
12's nextIncreasingValue: -1

Implementation:

for(int i = 0; i < array.length; i++) {
        int nextIncreasingValue = -1;
    for (int j = i + 1; j < array.length; j++) {
        if(array[j] > array[i]) {
            nextIncreasingValue  = array[j];
            break;
        }  
    }
    PRINT("For " + i + "th next increasing value is: " + j)
}

Now I want to know the time complexity of this program, since each time inner for loop is skipping some of the elements on iteration. So it cannot be O(n^2) even in the worst case.

Kindly explain me what will be the time complexity?

O(n) Solution using stack:

Stack s = new Stack();
for(int i = 0; i < array.length; i++) {
   while(!s.isEmpty() && array[i] > s.peek()) {
         PRINT  s.pop() NIV is array[i];
   }
   s.push(array[i]);
}
while(!s.isEmpty()) 
   PRINT  s.pop() NIV is -1;

Answer 1

It is $O(n^2)$. Consider array = [n, n-1, n-2, ..., 1].

---

BTW, you could implement this in $O(n)$ by scanning from the end of the array:

• Suppose the next-increasing-value (NIV) of a[i+1] is x.
• We want to find the NIV of a[i], which we observe that:
  1. If a[i+1] > a[i], then the NIV is a[i+1]
  2. If x > a[i], then the NIV is x
  3. Otherwise, a[i] is already the maximum value, so the NIV = -1.

Using this we could work backward from a[n-1] to a[0] to find the NIV of each entry in $O(n)$ time.

Answer 2

This should be a comment, but I don't have that rep yet on this stackexchange.

kennytm's answer is right, I just want to add my rule of thumb:

whenever you are iterating over an array/list/other linear data structure, regardless of how many elements you skip or how early you break out, the big-O notation is always O(n). Whenever you call that iteration from another loop, regardless of how far into the array you start, or how quickly you break out, it becomes O(n^2). Maybe you can see the pattern now.