# Little O notation relationship

Given the functions $$𝑓(𝑛)=𝑛^{n}$$ and $$𝑔(𝑛)=10^{10n}$$, I am trying to establish the following relationship: $$𝑓(𝑛)\notin o(𝑔(𝑛))$$.

I know to show for the opposite, $$𝑓(𝑛)\in o(𝑔(𝑛))$$, I would need to choos $$c$$ and $$n_{0}$$ such that $$\exists$$ $$c$$, $$\exists$$ $$n_{0}$$, $$\forall n\geq{n_{0}}$$ then $$f(n)\leq c. g(n)$$, but how should I choose $$c$$ and $$n_{0}$$. Note that I am beginner in studying CS and any help would be greatly appreciated.

## 3 Answers

One possibility is to merely apply the definition. That is, we see that if $$\lim_{n \to \infty} f(n) / g(n) = 0$$, then $$f(n) = o(g(n))$$. Computing this, we have that $$\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $$f(n) = o(g(n))$$ does not hold.

Your formulation of $$f(n) \neq o(g(n))$$ is wrong.

Recall that $$f(n) = o(g(n))$$ if for all $$c > 0$$ there exists $$n_0$$ such that for all $$n \geq n_0$$, we have $$f(n) \leq cg(n)$$.

The negation of this is: there exists $$c > 0$$ such that for all $$n_0$$ there exists $$n \geq n_0$$ such that $$f(n) > cg(n)$$.

Take $$c = 1$$. Given $$n_0$$, let $$n = \max(n_0,10^{10}+1)$$. Then $$f(n) = n^n > (10^{10})^n = 10^{10n} = g(n).$$

start like this

$$n \ge 10^{10}$$, $$\forall n \ge10^{10}$$
raising exponent n on both side of inequality, we get
$$\implies n^n\ge10^{10n}, \forall n \ge10^{10}$$
$$\implies 10^{10n}\le n^n,\forall n\ge 10^{10}$$
$$\implies 10^{10n}=O(n^n)$$
$$\implies n^n \notin o(10^{10n})$$
Here the $$c=1$$ and $$n_0=10^{10}$$

The value of $$c$$ and $$n_0$$ must come from the derivation.