How to Fool the Plot-Inspection Heuristic

The two functions are of the same order, g = Θ(f), and neither one eventually dominates the other: they cross each other infinitely often, at x = e^{arctan 3 + kπ} for every k ∈ ℕ, i.e. at 3.5, 81, 1866, 42 800, 982 000, … — a new crossing every factor of e^π ≈ 23.

Note that this also means g ∼ f is false: the ratio g/f does not converge at all, it keeps oscillating between 1 − √(2/5) ≈ 0.368 and 1 + √(2/5) ≈ 1.632. So this is a pair of functions where Θ holds but ∼ does not — the same phenomenon as in the square-and-multiply cost, only much harder to spot from a picture.

The moral for reading measured running times: a plot can only ever show you a bounded range, and any claim about asymptotic behaviour is a claim about what happens beyond every bounded range. A plot can therefore suggest a growth rate, it can refute a claimed one if the deviation is already visible — but it can never establish one.