Want to know the time complexity inner for loop which is partially iterating the array 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 &lt; array.length; i++) {
        int nextIncreasingValue = -1;
    for (int j = i + 1; j &lt; array.length; j++) {
        if(array[j] &gt; 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 &lt; array.length; i++) {
   while(!s.isEmpty() &amp;&amp; array[i] &gt; s.peek()) {
         PRINT  s.pop() NIV is array[i];
   }
   s.push(array[i]);
}
while(!s.isEmpty()) 
   PRINT  s.pop() NIV is -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:


If a[i+1] &gt; a[i], then the NIV is a[i+1]
If x &gt; a[i], then the NIV is x
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.