0

Hi all

Is there anybody who can solve this problem? This is not a easy problem.

Problem:

Assume that George(S,X) is a function that returns a Boolean value, where S is a stack, and that the time complexity of George is O( log |S| ) , where |S| is the current size of the stack.

Consider the following block of pseudo code.

S <- - empty stack

For i from 1 to n do

Read (Xi)

While (S! = Ø) and George(S, Xi) do

Pop (S)

End while

Push Xi onto S

End for

Assume that reading popping and pushing take O (1) time.

Use Amortized analysis to prove that the block of code runs in O (n logn) time.

Please describe your answer in detail if you know the solution.

Any help is appreciated.