amortized analysis time complexity problem

[chits12345]

Hi all

Is there anybody who can solve this problem? This is not a easy problem. (At least not for me.)

Here is the 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.

[Chipmunk Baby]

sumof(1-n)
{
one long stick is chopped from time to time pieces
}
The pieces is always smaller than n. Just pick up fast logn then the answer is nlogn.
Why so not n/2, n/5, n/100 for example, you may wonder. I answer because its more elegant to use nlogn than those :D