The simplified, closed-form (non-tautological) Big-O estimates for the…

Concept: For an n-term product like n! = 1 x 2 x ... x n, a simple (though loose) Big-O bound is obtained by replacing every factor with the largest one, n, giving n! <= nn. Independently, for a sum of logarithms such as log(n!) = sum_{k=1}^{n} log k, splitting the sum and bounding it above and below yields the classical result log(n!) = Theta(n log n) (this also follows from Stirling's approximation n! ~ sqrt(2*pi*n) * (n/e)n). Because any quantity is trivially a valid (though uninformative) Big-O bound for itself -- n! = O(n!) and log(n!) = O(log(n!)) always hold -- the closed-form estimate asked for here means a genuine expression in terms of n, not a restatement of the original factorial or log-factorial quantity.

Application:

1. Upper bound for log(n!): log(n!) = sum_{k=1}^{n} log k <= n log n, so log(n!) = O(n log n).

2. Lower bound for log(n!): summing only the terms from k = ceil(n/2) to n, each term is at least log(n/2), giving log(n!) >= (n/2) log(n/2) = Theta(n log n).

3. Combining the two bounds gives log(n!) = Theta(n log n), so the standard closed-form Big-O estimate for the logarithm term is O(n log n).

4. For the factorial term itself: since n! = 1 x 2 x ... x n and every factor is at most n, n! <= nn, so n! = O(nn). This is the standard closed-form (though loose) Big-O estimate used for this term, as opposed to writing O(n!) or O(log n!), which merely restate the original quantity instead of simplifying it into a closed form in n.

Cross-check: Cross-check via Stirling's approximation: n! ~ sqrt(2*pi*n) * (n/e)n, so log(n!) ~ n log n - n + O(log n) = Theta(n log n), confirming the summation-based bounds above. This also shows nn is a valid (if not tight) upper bound on n!, since (n/e)n <= nn for all n >= 1.

Answer: Matching the closed-form estimates derived above, n! = O(nn) and log(n!) = O(n log n).