Suppose we perform a sequence of stack operations on a stack whose size never exceeds kk. After every kk operations, we make a copy of the entire stack for backup purposes. Show that the cost of nn stack operations, including copying the stack, is O (n) O (n) by assigning suitable amortized costs to the various stack operations.

Question

Computers and Technology

Richards

10 October, 14:41

Suppose we perform a sequence of stack operations on a stack whose size never exceeds kk. After every kk operations, we make a copy of the entire stack for backup purposes. Show that the cost of nn stack operations, including copying the stack, is O (n) O (n) by assigning suitable amortized costs to the various stack operations.

+1

Answers (1)

Know the Answer?

Akira Krueger · Answer 1

The actual cost of (n) stack operations will be two (charge for push and pop)

Explanation:

The cost of (n) stack operations involves two charges which are actual cost of operation of the stack which includes charge for pop (poping an item into the stack) which is one and the charge for push (pushing an item into the stack) which is also one. and the charge for copy which is zero. therefore the maximum size of the stack operation can never exceed K because for every k operation there are k units left.

The amortized cost of the stack operation is constant 0 (1) and the cost of performing an operation on a stack made up of n elements will be assigned as 0 (n)