A few questions about the properties of $O(n)$, $o(n)$ and $\Theta(n)$

Question

I have started learning about calculational complexities, for now only about $o(n)$, $O(n)$ and $\Theta(n)$. I am wondering whether these properties are valid - my intuition tells me that this is the case. I do not need a formal proof, just the intuition. $$f(n) = o(g(n)) \Rightarrow f(n) = O(g(n))$$ $$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \land g(n) = O(f(n))$$ $$f(n) = O(n) \Rightarrow f(n) = O(n^2) \Rightarrow \dots \Rightarrow f(n) = O(n^k)$$ As I have already mentioned, I think that all of them are valid. Shoudl it not be the case, could you please present a counter-example?

Answer 1

$\bullet$ If $f(n)=o\left(g\left(n\right)\right)$ then for all $\epsilon>0$ it exists $N$ such as if $n>N$ $$ \left|f(n)\right|<\epsilon \left|g(n)\right| $$ choose $\epsilon = \pi$ ( random ) then $$ \left|f(n)\right|<\pi \left|g(n)\right| \Rightarrow f(n)=O(g(n)) $$

Answer 2

The first one is right; $o$ means that $f/g$ goes to zero while $O$ means that $f/g$ remains bounded.

The second one is right; $\Theta$ means that both $f/g$ and $g/f$ remain bounded.

Assuming that (as usual in complexity theory) the relevant limit is $n \to \infty$, the third one is right. The point is that $n^k$ grows much slower than $n^m$ if $k<m$.

Answer 3

The first $2$ are always true and the third is true when $x\to\infty$

---

In an informal language:

• $f(x)=O(g(x))$ means "$f(x)$ growth is at most asymptotically equal to $g(x)$ growth"

• $f(x)=o(g(x))$ means "$g(x)$ growth is infinitely faster than $f(x)$ growth"

• $f(x)=\Theta(g(x))$ means "$f(x)$ growth is asymptotically equal to $g(x)$ growth"

---

So if $f(x)=o(g(x))$ implies that $f(x)$ growth is less than asymptotic equal to $g(x)$ growth hence we have $f(x)=O(g(x))$

If $f(x)=\Theta(g(x))$ then $g(x)$ and $f(x)$ growth is asymptotic equal hence $g(x)=O(f(x))\land f(x)=O(g(x))$

When $x\to\infty$ $x^n$ growth is less than $x^{n+1}$ growth hence $f(n) = O(n) \implies f(n) = O(n^2) \implies \dots \implies f(n) = O(n^k)$