0 votes 0 votes 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) DS stack data-structures + – srestha asked Jan 13, 2017 srestha 5.4k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply saurabh rai commented Jan 13, 2017 reply Follow Share plzz think atleast once before ask u ll get 50% ans by urself.... https://gateoverflow.in/62056/complexity2 0 votes 0 votes vijaycs commented Jan 13, 2017 i edited by vijaycs Jan 13, 2017 reply Follow Share @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 ?? 0 votes 0 votes srestha commented Jan 13, 2017 reply Follow Share @saurabh this is not link for this question. I have some doubt in that question. Plz answer there 0 votes 0 votes srestha commented Jan 13, 2017 i edited by srestha Jan 13, 2017 reply Follow Share ....................................... 0 votes 0 votes IamRishabh commented Jan 13, 2017 reply Follow Share @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. 0 votes 0 votes saurabh rai commented Jan 13, 2017 reply Follow Share @vijay is it nt O(1) i think there is some typo in ur comment 1 votes 1 votes vijaycs commented Jan 13, 2017 reply Follow Share ^yes, I had written O(n) instead of O(1)... thanks :) 0 votes 0 votes IamRishabh commented Jan 13, 2017 reply Follow Share @ saurabh sir , then what is the right answer of this? 0 votes 0 votes saurabh rai commented Jan 13, 2017 reply Follow Share acc 2 me it is O(1) 0 votes 0 votes srestha commented Jan 13, 2017 reply Follow Share " a stack is implemented using an array " u all r talking about stack. how array is using here? 0 votes 0 votes saurabh rai commented Jan 13, 2017 reply Follow Share 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. 0 votes 0 votes srestha commented Jan 13, 2017 reply Follow Share 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)? 0 votes 0 votes saurabh rai commented Jan 13, 2017 reply Follow Share yes bcoz we have always value of Top 0 votes 0 votes srestha commented Jan 13, 2017 reply Follow Share But in array Say n th element deletion how much time will it take? 0 votes 0 votes Rahul Jain25 commented Jan 13, 2017 reply Follow Share 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). 0 votes 0 votes srestha commented Jan 13, 2017 reply Follow Share like stack how array do deletion in O(1) time? means in array we have to go from 1st element,rt? 0 votes 0 votes Rahul Jain25 commented Jan 13, 2017 reply Follow Share 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) 0 votes 0 votes Hradesh patel commented Jan 13, 2017 reply Follow Share i think here O(n) is correct 0 votes 0 votes Please log in or register to add a comment.