Compare 2^n^2 and 10^n asymptotically

Question

Prove that 10ⁿ  = o(2^{n^2})

Answer 1

lim(n->infinity)  10ⁿ/2^{n^2} 

= lim(n->infinity)  10ⁿ/(2ⁿ)^{n  =} lim(n->infinity)  (10/2ⁿ)^n = lim(n->infinity)  10/2ⁿ = 0

Answer 2

Here is my answer:
lim(n->infinite) (10^n/2^n^2) = lim(n->infinite)(1/2^(n*(n-2-log2.5)))
when n > (2+log2.5)/2 and n -> infinite, n*(n-2-log2.5)->infinite
so 2^n*(n-2-log2.5) -> infinite
as a result
lim(n->infinite) (10^n/2^n^2) = 1/infinite
                                             =  0

Comments

Merely f(n) < g(n) is not a proof that f(n) = o(g(n)), right?  For example we don't claim that n = o(n+1), simply because n < n+1.

---

Can you please elaborate how did you reach to the conclusion that (5/2) = (2^(log5/2)).

---

you may need to have a look at the definition of logarithm a^x = b
so x = loga(b). so a ^ loga(b) = b

---

ohk... got it
thanks...!

Answer 3

My Answer:

https://photos.google.com/share/AF1QipOb9rdGGhcoGpktz2ymf6BqDcc2nXQq5183vI_ghIDJWl06sScwz2czHZbB2PNe_A?key=VjQyNXJQc1QtTnBnb21ZQXhmSXNjT3p5aDJ3N29B

For the last point to prove:

if Lim n-> infty (log (f(n)) / log (g(n)) = 0, then lim (n-> infty(
(f(n)/g(n)) = 0

Here f(n) & g(n) are (+ve) monotonically increasing functions, i.e. for every value of n(>No) the rate of increasing of f(n)>g(n).

Now, if we take log on both the sides the formed equation would depict that log(f(n)) is greater than log(g(n)) for higher values of n.

So, as per my thought process if:

log(f(n)) > log(g(n))                              {assuming the base as 10}

then 10^f(n) > 10^g(n)                         {is also true}

So, we can jump to the conclusion that:

if Lim n-> infty (log (f(n)) / log (g(n)) = 0, then lim (n-> infty(
(f(n)/g(n)) = 0

Comments

I don't think "jumping to any conclusion" is needed :-).  Rather, if we go back to the definition of small oh (for all c, there exists n0, etc, etc), you can easily prove the claim, that I will post as a separate question, which then helps you prove this question.

Answer 4

My answer:

log both 10^n and 2^n^2

that is log(10^n) and log(2^n^2)

lim(n->infinite)(log(10^n)/log(2^n^2))

= lim(n->infinite)((n*log10)/n^2*log2)

= (log10/log2)lim(n->infinite)(1/n)

= 0 

So, 10ⁿ  = o(2^{n^2})