CODEWITHSUNDEEP
javaarraysstackqueuebig-o
user5447339
user5447339

Reputation:

Big O notation for Array/Stack/Queue

I am wondering, why Big O notation is O(1) for Array/Stack/Queue in avg. cases when we are inserting and deleting an element ?

In my understanding, it is O(1) because interting and deleting an element takes a constant amount of time no matter the amount of data in the set but I am still little bit confused. Any help will be highly appreciated in removing my confusion.

Upvotes: 1

Views: 13375

Answers (2)

lcch
lcch

Reputation: 3

For array based stacks, all operations are O(1) because you can only delete the item on top of the stack (you dont have to loop or iterate or do anything else). To insert is the same. For linked based stacks, they are also all O(1) except the destructor since you have to loop over the nodes and delete each one. For array-based ques, I am only sure that deque is O(N) since you return the first item and then you would move front.

I recommend watching this guy's videos, where he explains all of those in depth. Good luck!

Upvotes: 0

Žiga Sajovic
Žiga Sajovic

Reputation: 324

O(1) - notation means that the operation is performed in constant time.

O(n) - notation means the operation is performed in linear time, e.g. traversing a list.

Array

We start with the most obvious one. Array A has a fixed length n, and its elements can be accessed in constant time, by addressing the appropriate location in memory, i.e.

A[i]=10;

Stack

Stack is a Last in first out data structure. We always have a pointer/reference to the top element. So, even if the stack is implemented as a list, where we cannot address a specific element in it in constant time (we have to traverse the list in O(n)), we are accessing the topmost element with pop/peak, to which we have a pointer/reference and is thus accessible in constant time O(1).

Stack.pop(); //or peak() perhaps

Queue

Queue is a first in first out data structure. As with stack, accessing a specific element of the Queue can be done in linear time O(n), as we need to traverse it. But we usually have a pointer/reference to the first and last element of the queue. Therefore both enqueue and dequeue can be performed in constant time O(1).

Upvotes: 1

Related Questions