Example: a randomized algorithm was given and role of it, is to determines whether an input $a$ is a prime number?
This algorithm works in the following manner for one step:
I- If $a$ is prime, then our algorithm outputs YES
II- If $a$ is not prime, then our algorithm outputs NO with the probability $\frac{3}{4}$.
if we want to guarantee that achieve an output NO with the probability at least $1- \frac{1}{k}$ on step II, we should run this algorithm at least $O(\log k)$ times.
Note: first NO answer implies that a given input $a$ is not prime.
How this example solved? i.e: how $O(\log k)$ is determined?
Update:
we know the probability to tell yes in $x$ repeats of the algorithm on step II is $(\frac{1}{4})^x = 4^{-x} = 2^{-2x}$.
Best Answer
We know that the probability that it incorrectly answers "yes" on some composite in $n$ trials of the algorithm is $\left(\frac14\right)^n$ so the probability that it answers "no" at least once in $n$ runs is $1-\left(\frac14\right)^n$. Thus, we want to find $n$ such that $$1-\left(\frac14\right)^n\geq1-\frac1k$$ or $$\frac1k\geq\left(\frac14\right)^n$$ Taking logarithms, $$-\log k\geq -n\log4$$ or $$n\geq \frac{\log k}{\log4}=O(\log k)$$