# 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 < 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;

• Remember, big-O is an upper bound so even if the inner loop executed once for each iteration of the outer loop, we could still say the time complexity of the algorithm was $O(n^2)$ (even if it were actually a linear function of $n$). You probably should ask for the "best" big-O estimate or perhaps a big-Theta estimate. May 13 '16 at 14:10

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.

• Thanks! but i didn't understand what you are saying. May 13 '16 at 14:22
• @KanagaveluSugumar Which part are you confused with? May 13 '16 at 14:27
• 1) you told; It is O(n^2) ; but How? 2) you mentioned array with (n, n-1, ...), what you are explaining in this declaraion 3) How it is possible with O(n) using from the end? since i need next greater number... May 13 '16 at 14:31
• 1&2) The array demonstrates the worst-case scenario which your implementation requires $O(n^2)$ operations to complete. With a decreasing array it will never enter the if so the inner loop won't be break'en and there will be $O(n^2)$ operations. May 13 '16 at 14:34
• Yeah Thats good point :) but still the start point j is i+1 right; so increment of i will keep reducing j iteration correct na ..? May 13 '16 at 14:35

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.

• This is just wrong. First, there is no unique way of expressing a function using big-O. When you say that iterating over an array is always $O(n)$, that's kinda true but if, say, you break out after $\log n$ operations, it's also $O(\log n)$. And if you iterate inside another loop, the running time will depend entirely on how many times that loop iterates, which isn't necessarily $\Theta(n)$. May 13 '16 at 23:30