I Probabilistic Analysis and Randamoized Algorithms

Question 1

Q1. What is a probabilistic analysis?

Answer 1

Probabilistic analysis is the use of probability in the analysis of problems. Most
commonly, we use probabilistic analysis to analyze the running time of an algorithm.

Question 2

average-case running time:

Answer 2

In order to perform a probabilistic analysis, we
must use knowledge of, or make assumptions about, the distribution of the inputs.
Then we analyze our algorithm, computing an average-case running time, where
we take the average over the distribution of the possible inputs. Thus we are, in
effect, averaging the running time over all possible inputs. When reporting such a
running time, we will refer to it as the average-case running time.

Question 3

RNDOMIZED ALGORITHM

Answer 3

we call an algorithm randomized if its behavior is determined
not only by its input but also by values produced by a random-number generator.