How to calculate the Complexity of the Stack? Yes, I mean the various operations of Stack (Push, Pop). How it can be said that the complexity for these operations will be O(1).
- There is no such thing as "complexity of a stack". Perhaps you mean the complexity of the various operations (like push, pop)?PeterK– PeterK2010-11-29 12:09:39 +00:00Commented Nov 29, 2010 at 12:09
- What do you mean by "How to calculate"? Do you actually want to know the how the algorithmic complexity of stack operations is derived, or do you just want to know the answers?Marcelo Cantos– Marcelo Cantos2010-11-29 12:11:54 +00:00Commented Nov 29, 2010 at 12:11
- I'm tempted to invoke "No question too basic" on this, but I'm not sure what good it would do to reopen it: the OP seems to be either unclear on how complexity analysis is done or unclear on what kinds of implementations are used for stacks. I mean, I can write a stack that is O(n) for push and pop, it would just be really silly. @Temp: Can you clarify what you do understand about the problem?dmckee --- ex-moderator kitten– dmckee --- ex-moderator kitten2010-11-30 07:12:19 +00:00Commented Nov 30, 2010 at 7:12
Add a comment |
1 Answer
Pop
Θ(1)Push
Θ(1)
Because this operations not depends on size of stack and not depends on nothing.
2 Comments
Temp
Yes, I mean the various operations of Stack (Push, Pop). How it can be said that the complexity for these operations will be O(1).
Svisstack
@0xA3: stack is not a interface is a algorithm and in not invalid implementation all operations on her is in constant time not depending on number of elements.