What is the complexity of this algorithm

Question

This algorithm takes as input a vector of integers and will store the max first, let's stay its position is p in the array, then we store the max element in the range [p, n[ and so on.

// input v[0]...v[n-1] is a vector of integers already filled.
// output : stack s 
stack<int> s;
for(auto x: v){
     while(!s.empty() && x > s.top()) s.pop();
     s.push(x);
}

I can't figure out the worst case, but it seems the algorithm is linear, because the more the while() will work the more the stack size will be reduced and make the future work very cheap.

invisal · Accepted Answer · 2015-10-14 03:42:47Z

1

Worst Case

Your program is to have the max value at the bottom of the stack. You will perform push() operation N time. At worst case, you will pop() N-1 times . (because you cannot pop more than N-1 times or else you will have empty stack and it is against the program purpose).

Best Case

The best case would be when the max value at the first element of the vector V. You still perform N push() operation and will never perform any pop() operation.

So at the end of the day, regardless of any data in vector V, it will perform at the linear time.

answered Oct 14, 2015 at 3:42

invisal

11.2k4 gold badges36 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What is the complexity of this algorithm

1 Answer 1

Worst Case

Best Case

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Worst Case

Best Case

Comments

Your Answer

Sign up or log in

Post as a guest

Related