Question

An ordered stack is a data structure that stores a sequence of items and supports the following operations. ORDERPUSH(x) removes all items smaller than x from the beginning of the sequence and then adds x to the beginning of the sequence. Pop deletes and returns the first item in the sequence (or NULL if the sequence is empty). Suppose we implement an ordered stack with a simple linked list, using the obvious ORDERPUSH and Pop algorithms. Prove that if we start with an empty data structure, the amortized cost of each ORDERPUSH or Pop operation is O(1).

Answer 1

4. The process of analyzing the time complexity of the algorithms and determining the amount of time and memory space is taken by the algorithm is known as Amortized Analysis. • It defines the average code using the aggregate analysis. • In the aggregate analysis, the worst-case time complexity for a sequence of n operations is T(n). • The average cost per operation in the worst-case is T(n)/n. An ordered stack is used to store a sequence of items in Last-In-First-Out manner. Let the stack contains the following elements. Here, the top of the stack is 4.

Implement of orderedPush() using a simple linked list is shown below: //Define a structure for node of the //single linked list. struct Node { int data; struct Node* link; struct Node* top; //points to top element of stack. I orderedPush(x) - removes all items smaller than x from the //beginning of the sequence and then adds x to the beginning of the sequence. void orderedPush(int x) // create new node struct Node* temp; temp = new Node(); //the peek() function gives the value at the beginning of the sequence I/if the value at the beginning of the sequence <x, then pop that value. while ((top != NULL)&& peek() < x) popO;

// check if stack (heap) is not full. if (temp) //add x to the beginning of the sequence. temp->data = x; temp->link = top; top = temp; For the operation orderedPush(5), here, x = 5 and peek value is 6. The condition 6<5 fails. For the operation orderedPush(3), here, x = 3 and peek value is 5. The condition 5<3 fails. No element is popped. For the operation orderedPush(1), here, x = 1 and peek value is 3. The condition 3<1 fails. No element is popped. For the operation orderedPush(0), here, x = 0 and peek value is 2. The condition 2<0 fails. No element is popped. For the operation orderedPush(7), here, x= 7 and peek value is 4. The condition 4<7 true. So, the element is popped from the stack and 7 occupies the top of the stack.

As, there are 5 elements in the stack, it requires 5 operations to compare the value in the stack Here, the cost of each operation is T(1). Then the cost of 5 operation is T(5). The average cost is T(5)/5 =1 Implement of Pop using a simple linked list is shown below: //Pop deletes and returns the first item in the //sequence (or NULL if the sequence is empty). int popo struct Node* temp; l/if stack is empty, exit if (top == NULL) return NULL; temp = top; top = top->link; temp->link = NULL; return top->data;

The Pop operation deletes the first item in the stack. As, there are 5 elements in the stack, it requires 5 operations to empty the stack/ Here, the cost of each operation is T(1). Then the cost of 5 operation is T(5). The average cost is T(5)/5 =1 Therefore, the amortized cost of each ORDERPUSH or Pop operation is O(1).