Suppose you have a randomized algorithm whose number of steps is given by $T(n) = 2n^3 + 17$ and whose success probability is 1/2. Someone presents you with a new algorithm whose number of steps is given by $U(n) = 2n^3 + n + 17$ with a success probability of 3/4. Which one would you choose? (Notice these are not complexity classes. These are the exact number of steps of each algorithm.)
I don't know how to approach this problem. What is involved here? I believe something might be missing here. For example, how many more steps am I willing to invest in order to increase the success probability by 1/100? I believe something like that might be involved.
You don't have to solve the problem. I'm more interested in understanding the question. The concrete case is just to clarify the question and make it clear any of my misunderstandings.
Let $N_T$ and $N_U$, respectively, be the number of trials for success. $N_T$ and $N_U$ have geometric distributions, so $\mathbb{E}[N_T] = 2$ and $\mathbb{E}[N_U] = \dfrac{4}{3}$. The times to success are then $TN_T$ and $UN_U$. One could then choose the algorithm with the lesser expected time to success, i.e., $2T(n)$ vs $\dfrac{4}{3}U(n)$. Comparing the two one can see that the U-algorithm is always better.