/sci/ - Science & Math » Thread #11488863

3KiB, 197x24, Udklip.png

View Same Google iqdb SauceNAO

Big O

Anonymous Sat 21 Mar 11:13:07 2020 No.11488863 View Reply Original Report

Quoted By: >>11488885 >>11488942 >>11489090

Can someone explain to me why n^log(2)n is in O(2^n)?

I have to argue mathematically that n^log(2)n / 2^n is at most a constant. I have no idea.

Anonymous

Anonymous Sat 21 Mar 2020 11:21:28 No.11488885 Report

Quoted By:

>>11488863
How about using $n = 2^{\log_2 n}?$

Anonymous

Anonymous Sat 21 Mar 2020 11:31:12 No.11488908 Report

Quoted By:

What do you base that one? How would you know to use that?

Anonymous

Anonymous Sat 21 Mar 2020 11:51:19 No.11488942 Report

Quoted By: >>11488979

>>11488863
$ \log_2(n) \\ = 2 \log_2(\sqrt{n}) \\ = \frac{2}{\log(2)} \int_1^\sqrt{n} \frac{1}{x} dx \\ \leq \frac{2 \sqrt{n}}{\log(2)} $

$ n^{\log_2(n)} \\ = 2^{\log_2(n^{\log_2(n)})} \\ = 2^{\log_2(n)^2} \\ \leq 2^{\frac{4}{\log(2)^2} n} $

Anonymous

Anonymous Sat 21 Mar 2020 12:09:08 No.11488979 Report

Quoted By:

>>11488942

Hmm, I understand the majority of the math I think, I just can't see the formal arguments. Are there any chance you could use some words to describe what happnes?

thanks

Anonymous

Anonymous Sat 21 Mar 2020 12:32:23 No.11489016 Report

Quoted By:

Bump. Pliz help :)

Anonymous

Anonymous Sat 21 Mar 2020 13:15:37 No.11489090 Report

Quoted By:

>>11488863
$n^{\log _{2}(n)} = (2^{\log _{2}(n)})^{\log _{2}(n)} = 2^{(\log _{2}(n))^{2}}$
If you want to show $n^{\log _{2}(n)}$ is $\mathcal{O}(2^{n})$ , you can do that by showing $(\log _{2}(n))^{2} < n$ for n sufficiently large.

Anonymous

Anonymous Sat 21 Mar 2020 17:17:41 No.11489608 Report

Quoted By:

Isn't giving $\lim_{x \rightarrow \infty} \frac{f(x)}{O(x)} = 0$ enough?

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches