CODEWITHSUNDEEP
data-structurestime-complexity
user3789200
user3789200

Reputation: 1186

pop , push and multipop complexity

I'm bit confused with calculating the cost of pop and push in data structures.

1) It says, push(x): implementation as usual, Θ(1) time

Does this mean, if one push operation is done Θ(1) time, if 2 operations done,Θ(2) time, and if n push operations done Θ(n) times?

2) multipop(k): calls pop() up to k times, Θ(k) worst-case time

This is like remove k top objects from stack S. How does Θ(k) comes? since k objects are popped out the time will be Θ(k).

3) This is the most confusing part. Start from empty and perform m operations. What is the total time?

at most m pushes, m pops: total O(m). How does this comes O(m). Since there are 2m operations, doesn't it need to be O(2m).

Therefore during the worst case doesn't it need to be O(2m).

4) Here is another statement. This is too bit confusing

How about a sequence of n PUSH, POP and MULTIPOP operations? If stack is initially empty, Worst case operation is O(n) for MULTIPOP.

Therefore sequence of n operation can cost O(n*n)

Can someone please explain how this happens?

Upvotes: 0

Views: 8709

Answers (2)

Deshwal
Deshwal

Reputation: 11

1) The time complexity of push operation in a stack for array based implementation - best case: o(1) worst case: o(n) // when array becomes full average case: o(1)

push(x) operation has average case time complexity o(1) which doesn't depend on how many times you call.

2) similarly pop() operation has o(1) time complexity for every case which doesn't depend on how many times you call that function.

3) Big O gives us the time complexity in terms of input (n). for more refer: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/

4) The time complexity for any operation doesn't depend on the number of time you call that function it depends on the input (n).

Upvotes: -1

karastojko
karastojko

Reputation: 1181

  1. If push is of complexity O(1), it means that running time is less than some constant C > 0. Therefore, for n operations the running time is less than nC, so the complexity is O(n).
  2. Multipop calls pop k times, since pop has complexity O(1), the running time of multipop is k O(1) = O(k).
  3. O(2m) = O(m), because constants don't matter when complexities are calculated.
  4. Worst case complexity is O(n^2), since multipop is of complexity O(n) and push/pop of O(1). However, for sequence of operations the Amortized Analysis is often used, and in this case the amortized complexity for sequence of push, pop and multipop is O(n).

Upvotes: 2

Related Questions