# 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?