0
$\begingroup$

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.

Thank you in advance.

Improve this question
$\endgroup$
5
  • $\begingroup$ Have you tried anything? $\endgroup$
    – zkutch
    Jul 10, 2022 at 15:06
  • $\begingroup$ 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. $\endgroup$
    – roeas
    Jul 10, 2022 at 15:37
  • $\begingroup$ in the first example is it (2n)^(3n) or 2n^3n ? $\endgroup$
    – Rinkesh P
    Jul 10, 2022 at 16:24
  • $\begingroup$ It is nlog(2n)^(3n) $\endgroup$
    – roeas
    Jul 10, 2022 at 16:57
  • $\begingroup$ cs.stackexchange.com/q/824/755 $\endgroup$
    – D.W. ♦
    Jul 11, 2022 at 0:30

1 Answer 1

Reset to default
0
$\begingroup$

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}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I understand that (2n)^3n is the dominant term. Is that why we just need to concentrate on (2n)^3n and n!? If that is the case, then only O(g(n)) is true, isn't it? $\endgroup$
    – roeas
    Jul 10, 2022 at 19:56
  • $\begingroup$ Yes. Written inequality implies $n \log n! < n \log (2n)^{3n}$ for logarithm with base $>1$. $\endgroup$
    – zkutch
    Jul 10, 2022 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.