Question

Assume you had to implement a stack-like ADT in which pop() always returns the largest element. Let A be an array and n be the number of elements currently in the array. Suppose a student’s array-based implementation performs the push() function as follows:

• Call Binary-Search(x, A, n) to locate the index i in the array A at which x should be inserted to keep A sorted in ascending order.
• Shift the elements at indices i through n – 1 one position to the right to make room for x.
• Write x to A[i] and increment n.

Analyze the running time of push(). Provide Big-Oh, Big-Omega, and, if appropriate, Big-Theta bounds. Justify your answer. Assume the array is large enough that resizing is never necessary.

Here is some more info about pop(). The pop() operator returns the largest element rather than the element most recently pushed. For this to make sense, the objects on the stack must be totally ordered (e.g. numbers). Your implementations should be as time and space efficient as you can manage.

Answer 1

HERE WE ARE ASSUMING THAT IF POP ALWAYS OUTPUT THE LARGEST ELEMENT THEN WE CAN SAY THAT OUR INSERTION IS ALWAYS RUNS ON THE BACK OF INSERTION SORT IT MEANS THAT THE TOP MOST ELEMENT WILL ALWAYS BE LARGEST ELEMENT

PUSH RUN TIME:

The Big-Oh running time of push will be O(n) because according to our statement if a smallest number is entered it will be shifted to the bottom of the stack making the run time of the stack as O(n).

   The Big-Theta running time of push will be O(n/2) taking an example 1 and 3 are inserted in the stack and we are inserting 2 then we have to shift 3 to right and then insert it is taking average time which is O(n/2)

   The Big-Omega is O(1) if stack is empty and we are pushing first element then the run time will be O(1)

POP:

public int pop() { top --;

return stack[top];

}

IF YOU HAVE ANY QUERY PLEASE COMMENT DOWN BELOW

PLEASE GIVE A THUMBS UP