derandomize a BPP algorithm
Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is not what this exercise is asking you to do. The algorithm $B$ is still randomized – only its running time is deterministic.
Suppose that $A$ decides the problem $L$, in the following sense: if $x \in L$ then $\Pr[A(x) = 1] \geq 2/3$, and if $x \notin L$ then $\Pr[A(x) = 0] \geq 2/3$. Moreover, there is a function $f(n) = O(n^2)$ such that the expected running time of $A$ on $x$ is always at most $f(|x|)$. We want to construct a new algorithm $B$ with the same behavior regarding to $L$, and with the following additional property: there is a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$.
Suppose that $f(n) = Cn^2$, and consider your solution with $K = 3C$ and $q=1/2$. If we're careful, then there will exist a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$. What about the other property?
Suppose that $x \in L$ has size $|x|=n$. The expected running time of $A$ on $x$ is at most $f(n) = Cn^2$, and so $A$ terminates within $Kn^2$ steps with probability $p \geq 2/3$. If this happens, the probability that $B$ outputs $1$ is at least $2/3$. Otherwise, the probability that $B$ outputs $1$ is $1/2$. In total, $$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} &gt; \frac{1}{2}.$$
Similarly, if $x \notin L$ then $\Pr[B(x) = 0] \geq 11/18$. This is almost what we want – we want $11/18$ to be replaced by $2/3$.
In order to enhance the success probability (&quot;error reduction&quot;), we need to run $A$ several times and take a majority vote. By running $A$ enough times and by increasing the value of $K$, we get drive the error probability of $B$ down to any positive constant. Details left to you.