CODEWITHSUNDEEP
c++algorithmcomplexity-theory
zeralight
zeralight

Reputation: 710

What is the complexity of this algorithm

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.

Upvotes: 0

Views: 72

Answers (1)

invisal
invisal

Reputation: 11171

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.

Upvotes: 1

Related Questions