I am studying approximate Riemann solvers and often the motivation is that Godunov's method can be expensive to carry out, but I cannot see why. Say we have $$u_t + [f(u)]_x = 0$$
To my understanding, Godunov's method amounts to simple function evaluations and if-then statements (i.e. compare $f(u_L)$ and $f(u_R)$), so what part of the method is expensive exactly? I have also read that part of this cost comes from having to run Godunov's method for many iterations, but why? Is the method not deterministic?
Assuming you mean with Godunov's method the Godunov Flux $$ F (u_L, u_R) = \begin{cases} \min_{u_L \leq \theta \leq u_R} f(\theta) & u_L \leq u_R \\ \max_{u_R \leq \theta \leq u_L} f(\theta) & u_R < u_L \end{cases} $$ as used in the finite volume method, you see that you have to solve a global optimization problem of an arbitrarily complex function $f(u)$. The term global refers here to the fact that you need to find the global extrema (although on a restricted "local" interval). Deterministic global optimization is an active branch of research on its own. This is the main reason why people do not use it in FVM calculations nowadays since the optimization is in general way to costly.
You might have seen a version like presented here (Equation 4.15) for convex or concave functions. Then it is true that you just have to compare some points, yes.