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$
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, privacy policy and cookie policy

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