Consider the following functions: f(n) = 3n√n g(n) = 2√n log₂ n h(n) = n!…

Concept. Big-O states an upper bound in the limit: t(n) is O(u(n)) exactly when constants c > 0 and n0 exist such that t(n) ≤ c·u(n) for every n ≥ n0. Two consequences follow straight from that definition. A fixed positive constant factor never changes the bound, so if t(n) = k·u(n) for a constant k > 0, then each of the two functions is O of the other. And two powers of the same base are compared through their exponents, using axy = (ax)y together with 2log₂ n = n.

Application. The three functions are put on one common scale before any of the four statements is examined.

1. Rewrite g(n) as a power of n: 2√n log₂ n = 2log₂ n · √n = (2log₂ n)√n = n√n, because 2log₂ n = n.

2. Compare that with f(n): f(n) = 3n√n = 3·g(n), so the two differ by nothing more than the fixed factor 3.

3. Apply the constant-factor consequence: f(n) ≤ 3·g(n) for every n ≥ 1, so f(n) is O(g(n)) with c = 3 and n0 = 1; symmetrically g(n) ≤ f(n), so g(n) is O(f(n)) as well. The two functions are of the same order, f(n) = Θ(g(n)).

4. Put h(n) = n! on the same scale: by Stirling’s approximation log2(n!) = Θ(n·log2 n), while log2 g(n) = √n·log2 n exactly. The ratio of those two magnitudes is therefore Θ(√n), which grows without bound, so log2(n!) − log2 g(n) → ∞ and hence n!/g(n) → ∞. Since f(n) = 3g(n), n!/f(n) → ∞ as well.

Cross-check. Each of the four statements is now settled against those magnitudes.

Result. The single true statement is that f(n) is O(g(n)).

Common slip. The shape of g(n) looks exponential, which invites the reading that it outgrows the polynomial-looking f(n). Rewriting 2√n log₂ n as n√n removes that impression: its exponent √n·log2 n is a base-2 logarithm scaled by √n, not a constant multiple of n.