1
$\begingroup$

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;
Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rick Decker May 13 '16 at 14:10
7
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks! but i didn't understand what you are saying. $\endgroup$ – Kanagavelu Sugumar May 13 '16 at 14:22
  • $\begingroup$ @KanagaveluSugumar Which part are you confused with? $\endgroup$ – kennytm May 13 '16 at 14:27
  • $\begingroup$ 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... $\endgroup$ – Kanagavelu Sugumar May 13 '16 at 14:31
  • $\begingroup$ 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. $\endgroup$ – kennytm May 13 '16 at 14:34
  • $\begingroup$ 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 ..? $\endgroup$ – Kanagavelu Sugumar May 13 '16 at 14:35
0
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – David Richerby May 13 '16 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.