1. There is a function that is both O(n^2) and Omega(n^3). 2. Given two functions f(n) and g(n), if g(n)=O(f(n)) and f(n)=O(n^2), then g(n)=O(n^5). 3. Given two functions f(n) and g(n), if g(n)=O(f(n)) and f(n)=O(n^2), then g(n)=Omega(n).

1. There is a function that is both $O\left({n}^{2}\right)$ and $\mathrm{\Omega }\left({n}^{3}\right)$.
2. Given two functions f(n) and g(n), if $g\left(n\right)=O\left(f\left(n\right)\right)$ and $f\left(n\right)=O\left({n}^{2}\right)$, then $g\left(n\right)=O\left({n}^{5}\right)$.
3. Given two functions f(n) and g(n), if $g\left(n\right)=O\left(f\left(n\right)\right)$ and $f\left(n\right)=O\left({n}^{2}\right)$, then $g\left(n\right)=\mathrm{\Omega }\left(n\right)$.
I think the first one is false, but not sure about other two. Can anyone help me?
You can still ask an expert for help

Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Jorge Franklin
Step 1
You’re right about the first one; I’ll prove it. Then I’ll point you in the right direction for the other two; see if you can finish them on your own, but if you get stuck, feel free to leave a comment.
1. Suppose that f(n) is both $O\left({n}^{2}\right)$ and $\mathrm{\Omega }\left({n}^{3}\right)$. Then there are positive constants ${c}_{1}$ and ${c}_{2}$ and an $m\in \mathbb{N}$ such that $|f\left(n\right)|\le {c}_{1}{n}^{2}$ and $|f\left(n\right)|\ge {c}_{2}{n}^{3}$ for all $n\ge m$. But then for all $n\ge m$ we must have c2n3≤|f(n)|≤c1n2and hence $n\ge m$, which is clearly false when ${c}_{2}{n}^{3}\le |f\left(n\right)|\le {c}_{1}{n}^{2}$. Thus, there is no such f(n): you were correct.
2. The hypotheses imply that there are ${c}_{1},{c}_{2}>0$ and $m\in \mathbb{N}$ such that $|g\left(n\right)|\le {c}_{1}|f\left(n\right)|$ and $|f\left(n\right)|\le {c}_{2}{n}^{2}$ for all $n\ge m$. Can you find an inequality relating |g(n)| to ${n}^{2}$? What about to ${n}^{5}$?
3. What if f and g are both constant functions?