/sci/ - Science & Math » Thread #12475489

7KiB, 323x77, file.png

View Same Google iqdb SauceNAO

Find complexity of this recurrence relation

Anonymous Thu 17 Dec 09:42:05 2020 No.12475489 View Reply Original Report

Quoted By: >>12475509 >>12475526 >>12475554

Anonymous

Anonymous Thu 17 Dec 2020 09:50:44 No.12475502 Report

Quoted By:

at least 1

Anonymous

Anonymous Thu 17 Dec 2020 09:58:04 No.12475509 Report

Quoted By:

>>12475489
n

Anonymous

Anonymous Thu 17 Dec 2020 10:16:50 No.12475526 Report

Quoted By:

>>12475489
ngl my dude it looks decently complex

Anonymous

Anonymous Thu 17 Dec 2020 10:22:48 No.12475531 Report

Quoted By:

i think trial and error does show its n

Anonymous

Anonymous Thu 17 Dec 2020 10:38:36 No.12475554 Report

Quoted By:

>>12475489
found

Anonymous

Anonymous Thu 17 Dec 2020 10:57:33 No.12475571 Report

Quoted By: >>12475590

T(n) = O(n * log(log(n)))

Anonymous

Anonymous Thu 17 Dec 2020 10:58:46 No.12475573 Report

Quoted By:

Sent ;)

Anonymous

Anonymous Thu 17 Dec 2020 11:06:09 No.12475590 Report

Quoted By:

>>12475571
If you plug in
$T(n) = \frac{n}{\log(2)} \log(\log(n))$
then
$T(n) = \sqrt{n} T(\sqrt{n}) + n$
exactly for n>1.

Anonymous

Anonymous Thu 17 Dec 2020 11:25:11 No.12475626 Report

Quoted By:

$T(n)=n+n^{1/2}T(n^{1/2})$
$=n+n^{1/2}[n^{1/2}+n^{1/4}T(n^{1/4})]$
$=n+n+n^{3/4} [n^{1/4}+n^{1/8}T(n^{1/8})]$
$=n+n+...+n^{0.999...}[n^0+n^0T(n^0)]$
$=(\infty+c)n$

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