Big O- and Omega-Notation for functions

I want to find out how to check, if the following relationships are true or false.

f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false;

f(n) = 3n^2; g(n) = 9^(base3-logn); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false;

I am very new to this topic, so i would be very grateful, if someone could explain it to me. If something is not understandable, don't hesitate and ask me.

• Have you tried anything? Jul 10, 2022 at 15:06
• Yes, but I am absolutely unsure about the result. Second example: I simplified g(n) and got n^2. From this I conclude that g(n) is an upper bound for f(n) and O(g(n)) is valid. Since, to my knowledge, prefactors are negligible in the dominant term, I would say at this point that g(n) is also a lower bound for f(n). But it is exactly at this point that I have the big uncertainty. Jul 10, 2022 at 15:37
• in the first example is it (2n)^(3n) or 2n^3n ? Jul 10, 2022 at 16:24
• It is nlog(2n)^(3n) Jul 10, 2022 at 16:57
In second example if you have $$f(n)=3n^2$$ and $$g(n)=n^2$$, then, of course $$f(n)=\Theta(g(n))$$.
For first enough to note, that $$n! < (2n)^{3n}$$.
• Yes. Written inequality implies $n \log n! < n \log (2n)^{3n}$ for logarithm with base $>1$. Jul 10, 2022 at 23:18