[Solved]: Want to know the time complexity inner for loop which is partially iterating the array

Problem Detail: 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;

Asked By : Kanagavelu Sugumar

Answered By : kennytm

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57411 Ask a Question Download Related Notes/Documents