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.

If a train leaves the station @ 8:30 p.m. full of clowns named bob and larry and one named steve and it takes 1 hour to get there, the number of licks it will take to get to the center of a tootsie roll tootsie pop

= 42.

QED.

Comments
smartass :)

If a train leaves the station @ 8:30 p.m. full of clowns named bob and larry and one named steve and it takes 1 hour to get there, the number of licks it will take to get to the center of a tootsie roll tootsie pop

= 42.

QED.

Hi

I didn't get you. This is not the answer of my problem.Please be clear.

I didn't get you. This is not the answer of my problem.Please be clear.

okay... how about, "You need to quit relying on others to do your work, and do it yourself. When you have put forth some effort, and then get stuck, come back with a sensible question."

is that clear?

This article has been dead for over six months. Start a new discussion instead.