For the following function, find a function as simple as possible that reflects its asymptotic behavior

Question

Question: For the following function, find a function as simple as possible that reflects its asymptotic behavior (use big-notation). What does as simple as possible mean to begin with? A short definition would be helpful!

$$f(n) = 3^{2n-1} + 4^n + n^2 log(n!)$$

What I've did:

$3^{2n-1} \in O(2n)$

$4^n \in O(4^{n})$

$n^2 \in O(n^2)$

$\log(n!)\in O(max(log(n), 1) = O(log(n))$

And so

$n^2 \log(n!)\in O(max(n^2, log(n)) = O(n^2)$

Finally I get

$f(n)\in O(n^2 * 4^n * n^2 * 2n) = O(2*n^5*4n)$

Is this correct?

Answer 1

$3^{2n-1} \in O(2n)$ is quite false !

It's $3^{2n-1} \in O(9^n)$ (as $3^{2n}=9^n$, essentially) and his dominates $4^n$ in the second term and certainly everything polynomial and logarithmic.

So $f(n) \in O(9^n)$ is IMHO the simplest assymptotic form (single exponential term).

Answer 2

"Simple" is probably not formally defined. However, we can make an attempt: Given a formula, we could for example count the number of symbols, where each constant, variable, operation, function counts as one. Less symbols means simpler. Note that this is not directly a property of a function but of an expression for the formula.

Answer 3

When asked to find the asymptotic behavior, you can discard terms that are negligible in front of the dominant term. Here you have two exponentials, in base $4$ and $3^2$, and by Stirling we know that the third term is asymptotic to $n^3\log n$. Hence $3^{2n-1}$ is dominant (exponentials grow faster that polynomials) and

$$f(n)\in O(3^{2n-1}).$$

We can further simplify by noting that $3^{2n-1}=\dfrac{9^n}{3}$, and we can ignore the constant factor so that

$$f(n)\in O(9^n).$$