Problem 42

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Expected value vs probability

Due: February 15
Points: 3

I have two algorithms, A and B, that solve the same problem.

The expected running time of algorithm A is n steps (or seconds, or primitive operations, or whatever unit you like).

Algorithm B finishes in n steps at least 50% of the time.

Which algorithm would you rather use? If you say they are both equally good, explain why. Otherwise, say specifically why one would be preferable over the other, perhaps with an example to back up your point.