0

In Stack (LIFO) situation: If I use the command peek() in linked-list, the complexity is 0(n). Why is it so since I only read the last object of the list? Should it be 0(1)? In Queue (FIFO): If I use peek() in linked-list, the complexity is now 0(1). Why is there a difference?

Thanks for spending time for reading and helping.

Someonewhohaveacat
  • 83
  • 1
  • 3
  • 11

1 Answers1

0

Are you sure about that complexity? Accessing top element of the stack is 0(1), the same goes for all the operations like push() and pop() as they're independent from the size of the stack.

You would get 0(n) in case you'd want to access the bottom of the stack (since you'd need to go all the way down from the top element by element).

Where did you get that complexity from?

Dominik A. Sztorc
  • 1
  • 2
  • I learned this in my school, from my teacher . I have asked him again for sure. And he said it is right. I ask for an explaination but I did not understand. That's why I bring it here... – Someonewhohaveacat Mar 23 '17 at 18:22
  • The only explanation I can come up with is the case when with peek() is in fact a search that can find any element in the stack. In that case as I mentioned the complexity of that operation will be O(n) as you start from the top and look through the stack linearly element by element. However you should always have the direct access to the top of the stack. Here's an interesting post comparing complexity of operation of various structures: http://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures – Dominik A. Sztorc Mar 23 '17 at 19:36
  • Also, I suggest you check this as well: http://bigocheatsheet.com/ and here: https://en.wikipedia.org/wiki/Peek_(data_type_operation) Hope that helps. – Dominik A. Sztorc Mar 23 '17 at 19:42
  • Thank you. I am sure to take a look at those. – Someonewhohaveacat Mar 24 '17 at 18:47