0

I am learning algorithmic analysis and I want to know how to compare functions...I am trying to apply the definitions of Big Oh, Omega and theta yet unable to find the correct answer.

For example, how to know if $f(n) = 100n^{5.001} + n^5\log(n)^{10}$ is

(a) $O(n^{10})?$

(b) $\Theta(n^5\log(n))?$

(c) $\Theta(n^{5.001}\log(n))?$

(d) $\Omega(n^{5.001} + n^5\log(n))?$

(e) $\Omega(\sqrt n)?$

(f) $o(n^{5.1})?$

Arctic Char
  • 16,007
Slavbabushka69
  • 3

1 Answers1

0

Use this:$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\begin{cases}\infty,&g(n)\in o(f(n))\\c\ne0,&g(n)\in\Theta(f(n))\\0,&g(n)\in\omega(f(n))\end{cases}$$

Shubham Johri
  • 17,659
  • Thank you, It's the same for f(n) ∈ Ωg(n), f(n) ∈ Θ g(n), and f(n) ∈ O g(n), respectively based on the order of your answer. – Slavbabushka69 Oct 29 '20 at 00:02
  • @Blackmist You are welcome. Just remember that what I have written are if and only if conditions i.e. $\lim\to\infty\iff g(n)\in o(f(n))$. While $g(n)\in o(f(n))\implies g(n)\in O(f(n))$, the reverse implication is not true when $g(n)\in\Theta(f(n))$ and you are all good ^_^ – Shubham Johri Oct 29 '20 at 00:07
  • 1
    ohh okay, thank you for the clarification. Already knowing how to correctly solve them now :') – Slavbabushka69 Oct 29 '20 at 00:12