1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 28 at 17:26
  • $\begingroup$ I'm really, really sorry about this confusion. I said about "iterative algorithm" must call itself and must have a logarithmic running time; because I read this page: (en.wikipedia.org/wiki/Iterated_logarithm) and I read the title mistakenly as "iterated algorithm" instead of "iterated logarithm". So, I thought that "iterative algorithm" must has a logarithmic running time. I'm really sorry about this silly and very silly question. Huge Thanks Prof. Yuval to clarify my mistakes. Now, everything is very, very clear. $\endgroup$ – user777 Jun 30 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.