Stack

Question

Consider a stack is implemented using an array. What is worst case time complexity of push operation?

A) O(n)

B) O(log n)

C) O(n log n)

D) O(1)

Comments

plzz think atleast once before ask u ll get 50% ans by urself....
https://gateoverflow.in/62056/complexity2

---

@saurabh, At what index we need to do push operation... In general, in case of stack, we do push or pop operation at the top  which can be done in O(1) right ?? but if not necessarily at top index then ans would be O(n) ..right ??

---

@saurabh

this is not link for this question.
I have some doubt in that question.
Plz answer there

---

.......................................

---

@srestha i guess it must be "O(1)"  bcoz will be do push operation we just push on top , we dont push in between of the stack . even if we do some operation on stack element before pushing other element on stack it will also take constant time. so i guess worst case time complexity will  "O(1)".  correct me if i am wrong at any assumption.

---

@vijay is it nt O(1)
i think there is some typo in ur comment

---

^yes, I had written O(n) instead of O(1)... thanks :)

---

@ saurabh sir , then what is the right answer of this?

---

acc 2 me it is O(1)

---

" a stack is implemented using an array "

u all r talking about stack.

how array is using here?

---

srestha it is so simple to implement stack using array
   suppose we have a[5] to use size=5
now insert an element in array means push in to stack nd keep track to Top usin an integer ie index of that array.

---

but insert n th element in array takes O(N) time.

But in stack it is always O(1).

Moreover is deletion of arrays always takes O(1)?

---

yes bcoz we have always value of Top

---

But in array

Say n th element deletion

how much time will it take?

---

Stack does not delete nth element fist of all. It only deletes top element.

And we will be knowing value of n so deleting will take O(1) , but it might be required(depends on which DS yiu are implementing and space constraints) to shift all other elements, hence resulting in O(n).

---

like stack how array do deletion in O(1) time?

means in array we have to go from 1st element,rt?

---

I will use a variable top, whenever i will insert i will insert at array[top], increment top and whenver delete i will delte array[top] , bcoz i dont need to remember how many elements are there in stack , this top variable will be doing it.

Insert delete both in O(1)

---

i think here O(n) is correct