I know that big O is used to describe the upper bound of a function, so doesn't this mean that if the upper bounds f and g are the same, they are the same function? If this is the case, then we can say that f ∈ Θ(g) because if that were not the case, then the two upper bounds would not be the same and thus one would out grow the other. Is this correct?
Asked
Active
Viewed 679 times
-1
-
mb im new to stack exchange – Patrick Perkins Sep 21 '20 at 03:31
-
1Here is a MathJax tutorial (: – PinkyWay Sep 21 '20 at 05:01
-
1Why are you vandalizing your own question? – sai-kartik Sep 23 '20 at 02:05
-
3I’m voting to close this question because OP keeps vandalizing it for some reason. – Integrand Sep 24 '20 at 19:54
2 Answers
2
No, they need not be the same function: $O(5x^2)=O(x^2+x+7)$, for instance (and $5x^2\in\Theta(x^2+x+7)$).
You’re going to have to use the actual definitions of $O$ and $\Theta$; I’ll get you started. The definitions are given in slightly different forms in different sources, so I may be doing things a little differently from what you’re used to.
Suppose that $O(f)=O(g)$. Certainly $f\in O(f)$, so $f\in O(g)$. This means that there are constants $a_f$ and $c_f>0$ such that $|f(x)|\le c_f|g(x)|$ for all $x\ge a_f$. Similarly, $g\in O(g)$, so $g\in O(f)$, and therefore there are constants $a_g$ and $c_g>0$ such that $|g(x)|\le c_g|f(x)|$ for all $x\ge a_g$. Can you put these facts together to show that $f\in\Theta(g)$?
The proof in the other direction basically just reverses the argument.
Brian M. Scott
- 616,228
-
Ah ok that makes sense. I guess I was saying that f and g would be the same function because in computer science we drop constants and non dominant terms from functions. So in your example, the functions f(5^2) and g(^2++7) would both reduce down to x^2. That's why I said they are the same function. However, I am still probably wrong in assuming it is ok to reduce these functions in such a manner in this proof. – Patrick Perkins Sep 20 '20 at 19:52
-
@PatrickPerkins: Yes, for this proof you want to treat $f$ and $g$ as specific functions, even though we know, for instance, that if $f$ is a polynomial in $x$ of degree $n$, then $O(f)=O(x^n)$, and that $O(2^n+f(x))=O(2^n)$. This theorem is actually what justifies those equalities. – Brian M. Scott Sep 20 '20 at 19:55
0
$O(f)=O(g)$ means, that they are equal sets, so $\phi \in O(f) \Leftrightarrow \phi \in O(g)$ which is $|\phi| \leqslant C_1 |f| \Leftrightarrow |\phi| \leqslant C_2 |g|$. Because $f \in O(f)=O(g)$, then $f \in O(g)$, also $g \in O(f)$. Now if we take $f,g$ in place of $\phi$, then we obtain $f \in \Theta(g)$.
Now suppose $f \in \Theta(g)$, so we have $C_1|g| \leqslant |f| \leqslant C_2|g|$. If $\phi \in O(f)$, then $|\phi| \leqslant C_3|f|\leqslant C_3C_2|g| $ and so $\phi \in O(g)$, so $O(f) \subset O(g)$. Analogical way gives $O(g) \subset O(f)$.
zkutch
- 13,410