2. Algorithm and Running Time Analysis: Give the tightest possible upper bound f
ID: 3879733 • Letter: 2
Question
2. Algorithm and Running Time Analysis: Give the tightest possible upper bound for the worst case running time for each of the following in terms of N. Assume that the most time-efficient implementation is used. Pushing a value onto a stack containing N values, implemented as a linked list. Explanation a. b. Pushing a value onto a stack implemented as an array. Assume the array is of size 2N. Explanation: c. Enqueue a value onto a queue containing N values implemented as a circular array (as described in class). (Assume the array is size N+5.) Explanation Pop a value off a stack containing N elements implemented as an array. Explanation d.Explanation / Answer
A stack is a data structure which is used to store and remove elements. New elements are added from the top of the stack which is termed as push operation. Elements can be removed from the top of the stack which is termed as pop operation.
Stack can be implemented using linked list. Worst case running time for pushing a value onto a stack containing N values, when implemented as a linked list is O (1).
Algorithm
Stack can be implemented using array. We have to specify the size of array before implementation. Worst case running time for pushing a value onto a stack containing 2N values, when implemented as an array is O (2N). This is because, a new array must be allocated, when the array is full and the values must be copied.
Algorithm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.