# Questions about Randomized Median algorithm?

In textbook by Mitzenmacher and Upfal here, they write in page 62, the following:

By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time.

Note that that the algorithm has linear running time. Now, if we repeat this algorithm for k times, then the running time would be O(kn). Now, how they say that "By repeating algorithm until it succeeds in finding the median, we can obtain an iterative algorithm"? I do not understand how they get an iterative algorithm. In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

Another question: What does they mean by "it has a random running time"?

About iterated algorithm, please look here. To see the algorithm, look at the book in page 59.

Let's start with your second question. A random running time is a running time which is a random variables. As a simple example, consider an algorithm which tosses a fair coin until it come up heads. The running time is a random variable whose distribution is, roughly speaking, geometric. This is not so different from the randomized median algorithm: every run of the median algorithm is like a coin toss, and you iterate running it until it comes up "heads" (succeeds).

Now, for the name iterative algorithm. Here is the algorithm you describe:

repeat
run Algorithm 3.1
until the algorithm succeeds


This is the epitome of iteration – the algorithm consists of a single loop.

You write

In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

I'm not really sure why you think that an iterative algorithm should call itself. Indeed, algorithms calling themselves are usually known as recursive algorithms. (As an aside, an iteration of the form considered here is a special case of recursion known as tail recursion.)

Also, I'm not really sure why the algorithm should have a logarithmic running time. The standard algorithm for summing an array is iterative and runs in linear time.

• I suspect that some information is missing here – next time, try to include all relevant information in the post. Don't forget that we can't read your mind. – Yuval Filmus Jun 28 '19 at 17:26