2
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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). $$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.