
As you can see the randomized algorithms generally have much better time bounds

or well they might not seem much, but you already know that for exponential time algorithms

little differences here so 1.47 versus 1.32 actually makes quite a difference

so they have generally a lot better time bounds than the deterministic algorithms

It seems that randomized algorithms allows us to achieve

a better worstcase running time than deterministic algorithms.

Of course, up here it has the advantage that it's actually done after this amount of time

whereas down here, it's always an expected running time

and as I said you're gambling a little bit.

You cannot be 100% sure that the algorithm

has found a satisfying assignment even though there might be one.