For $f(n) = (2^n +n^n)(n^3+n\text{log}(n^n))$, what is the tightest big-O estimate?
My attempt is the following:
We can break this into two product statements: $(2^n +n^n) \text{ and }(n^3+n\text{log}(n^n))$
Focusing on the left most: $(2^n + n^n) \le (n^n + n^n) \text{ then } O(n^n)$
Now the right most: $n^3+n\text{log}(n^n) \rightarrow n^3 + n^2\text{log}(n) \le n^3 + n^3 \text{ then } O(n^3)$
Then all together we have: $O(n^{n+3})$
Is this the correct way to calculate this? Super new to this, and I have to admit, getting to the $O$ estimation is... strange, and I don't feel like my justification is correct.
The basic strategy is correct, but the way it's normally explain would be slightly different. Since $n\log(n^n)=n^2\log n\in o(n^3)$, $n^3+n\ln(n^n)\in O(n^3)$ (or which is stronger, $n^3+n\ln(n^n)\sim n^3$). Similarly, $2^n\in o(n^n)$ implies $2^n+n^n\sim n^n$. So $f\sim n^{n+3}$. This stronger than $f\in O(n^{n+3})$; it's also sufficient to prove no tighter big-$O$ characterization is possible.