Always a prime between $x$ and $x+cf(x)$ What is the asymptotically slowest growing function $f(x)$, such that there exists constants $a$ and $b$, such that for all $x>a$, there is always a prime between $x$ and $x+bf(x)$?
$f(x)=x$ works, does $\sqrt{x}$ work, $\log(x)$, or $\log\log(x)$?

What you are looking at is an upper bound for prime gaps.  Bertrands postulate states that there is always a prime between $x$ and $2x$, but this has been improved significantly.  The most recent result due to Baker Harman and Pintz states that $$\pi\left(x+x^{0.525}\right)
-\pi(x)\gg \frac{x^{0.525}}{\log x}.$$ This means that for sufficiently large $x$, there is always a prime between $x$ and $x+x^{0.525}$.  This implies for example that there is always a prime between consecutive cubes, that is there is always a prime in the interval $(x^3,(x+1)^3)$.
As for the expected result, the Wikipedia article covers this as well, see Conjectures about prime gaps.  In particular, the Riemann Hypothesis tells us that for any $\epsilon$, we will have a prime in the interval $(x,x+x^{\frac{1}{2}+\epsilon})$ for sufficiently large $x$.  Cramer made the much stronger conjecture that there is always be a prime between $x$ and $x+\log^2x$ for sufficiently large $x$.  
