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
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.

Any help is appreciated.

## All 4 Replies

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.

commented: smartass :) +25

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.

Hi

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

I think it was meant as a joke :)

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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.