UGC NET CSE | December 2006 | Part 2 | Question: 23

Question

What is the time required to insert an element in a stack with linked implementation ?

• A. $O (\log_2 n)$
• B. $O (n)$
• C. $O (n\log_2 n)$
• D. $O (1)$

Comments

here nothing is given about the order in which the element to be inserted , we just have to take the data from the list and push it onto the stack...since both operations requires constant time O(1) would be the correct answer...

Note:if n elements are to be inserted then complexity would be O(n).

---

O(1)

Answer 1

D is the answer

Since the operation will involve only a pointer modification which will take O(1)

Comments

o(1) will be answer as element that is to be inserted in front of  top pointer  and then top pointer is modified to point to that new inserted element

Answer 2

Insertion/PUSH is equivalent to the insertion of a node at the beginning of the linked list, which requires constant time. Just modification of two pointers. Therefore PUSH requires constant time.

Hence option D.