Confusion Big O notation -

Question

Question : Is this what this property of Big O Notation is trying to explain?

The Big O property , at the reference, it's the theorem 4,

It says :

Let $d,e,f,g : N \to R $ be functions. Then :

(4) $d(n) \in O(f(n))$ and $f(n) \in O(g(n)) $ then $d(n) \in O(g(n))$

My understanding :

$n^2 \in O(n^2) $ and $n^2 \in O(n^2) $ then $n^2 \in O(n^2)$

This seems correct but im not sure the theorem would be that simple. I feel im missing something.. Would someone ,please, clarify?

Reference : http://www.inf.ed.ac.uk/teaching/courses/cs2/LectureNotes/CS2Bh/ADS/02-03/lecture2.pdf

Answer 1

Another way to say this:

$d(n) \in O(f(n))$ means there is a $u > 0$ such that, for all large enough $n$, $|d(n)| \le u|f(n)|$.

Similarly, $f(n) \in O(g(n))$ means there is a $v > 0$ such that, for all large enough $n$, $|f(n)| \le v|g(n)|$.

Therefore, for all large enough $n$, $|d(n)| \le u|f(n)| \le uv|g(n)|$, so that $d(n) \in O(g(n))$, with a valid value for the constant being $uv$.

Answer 2

If $|d(n) / f(n)|$ remains bounded as $n \to \infty$ and so does $|f(n) / g(n)|$, then what can we say about $|d(n) / g(n)| = |d(n) / f(n)| \cdot |f(n) / g(n)|$?

Answer 3

It's more like a transitivity property of the big-O notation. A more suited example would be: $n \in O(n^2)$ and $n^2 \in O(n^3)$ so $n \in O(n^3)$.

Edit: you can also consider this example : $3n^2 + 3n \in O(n^2)$ and $n^2 \in O(n^3)$, so $3n^2 + 3n \in O(n^3)$