Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
An algorithm is randomized if the behavior is dependent not only on the input but also by values produced by random number generator. In analysis of randomized algorithm we use a random - number generator to produce the distribution of various input values. When we calculate the running time it will be for the distribution of various input values. In a sense we are calculating average time for the distribution of input values. We are in effect averaging running time for all possible input values. Randomization will reduce the chance of getting a worst case. It will be in correct measure if we use randomization to analyze worst-case running time.
No comments:
Post a Comment