3.Array

Question

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

give explanation

Comments

O(1). Just keep a pointer(index value) of the stack top. Let's say it "top". Initially top = 0. Assuming index starts with 0. To do a push, stack[top++] = item. To do a pop return stack[--top].

---

worst case and best case both will be O(1) rt?

---

Yes.

---

ok tnks :)

---

Is there any other implementation of stack using array other than usual optimal way?

Answer 1

O(1) in both worst and best case, ONLY if we have a pointer to the location where the next element is to be inserted in the STACK. Thereby, if we have to push a new element into the stack, we execute

a[pointer++] = elementValue.;

To pop and element, we execute,

poppedValue = a[--pointer];

--

Altough unlikely, if we have lost the pointer that was used to keep track of the top element of the stack, then obviously we have to search for the top most element and then push element into the stack. Time Complexity in that case is O(n).

--

Hope I am right. :P

Comments

what do u mean by "lost the pointer"??

---

i mean, if the pointer was overwritten by some other part of the program.