/sci/ - Science & Math » Thread #11505874

52KiB, 806x369, aub.png

View Same Google iqdb SauceNAO

Asymptotic Upper Bound of Recurrence

Anonymous Fri 27 Mar 08:45:52 2020 No.11505874 View Reply Original Report

Quoted By: >>11506859 >>11506952 >>11507098 >>11507252

I have no idea how to do any of these. If you can help me out on any of them it would be much appreciated. Deadline in 2 hours!

Anonymous

Anonymous Fri 27 Mar 2020 19:01:27 No.11506859 Report

Quoted By:

>>11505874
>CS shitters
a. linear
b. logarithmic
c. I'm sure you are familiar with muh special function from your major, I'd assume inverse of tetration or something
d. 2^n
e. linear
f. again, pay attention in class retard
g. 2^2^n I'm guessing
h. I bet your prof has a list of acceptable functions for you to pick and choose from
i. linear
do the rest on your own fucking trash
>justify
lmao. You don't have the math skills for that.

Anonymous

Anonymous Fri 27 Mar 2020 19:35:55 No.11506952 Report

Quoted By:

>>11505874
look up the master theorem already

Anonymous

Anonymous Fri 27 Mar 2020 20:46:37 No.11507098 Report

Quoted By: >>11507123

>>11505874
>>11505874
(a) T(n) = n
(b) T(n) = ln(n)
(c) T(n) = ln(ln(n))
(d) T(n) = 2^n
(e) T(n) = 2^ln(n)
(f) T(n) = 2^ln(ln(n))
(g) T(n) = 2^(2^n)
(h) T(n) = 2^(2^ln(n))
(i) T(n) = 2^(2^ln(ln(n)))
(j) T(n) = n*sum[from 0 to ln(n)](2^i) = 2^ln(n)*n+n
(k) T(n) = sum[from 0 to ln(n)] ((8/4)^i*log_4((8/4)^i)*n + (8/4)^i*log_4(n)*n) = sum[from 0 to ln(n)] (2^i*(1/2*i)*n + 2^i*1/2*ln(n)*n) = n(sum[to ln(n)] (2^(i-1)*i) + lg(n)*sum[to ln(n)](2^(i-1))) <= n*2*lg(n)*sum[to ln(n)](2^(i-1)) (>= n*1*lg(n)...) = n*lg(n)*sum[0 to ln(n)](2^i) = n*lg(n)*2(ln(n)+1)
(l) T(n) = n2*sum[from 0 to log_9(n)](3^i) = n2*(3^(log_9(n)-1)/2)

Anonymous

Anonymous Fri 27 Mar 2020 20:57:05 No.11507123 Report

Quoted By: >>11507186

>>11507098
2^ln(n) is linear, no?

Anonymous

Anonymous Fri 27 Mar 2020 21:25:12 No.11507186 Report

Quoted By:

>>11507123
Oh yes
2^ln(n) = n

Anonymous

Anonymous Fri 27 Mar 2020 21:53:28 No.11507252 Report

Quoted By:

>>11505874
>>11505874
Redoing k and l:
(k) T(n) = sum[to log_4(n)]((8/4)^i*n*log(n)) - sum[0 to log_4(n)]((8/4)^i*n*log(4^i) = nlog(n)*sum[to log_4(n)](2$ i) - n*log(4)*sum[to log_4n](i*2^i) = n*log(n)*2^(log_4(n)+1) - n*log(n) - n*log(4)*2^(log_4(n)+1)*log_4(n) + n*log(4)*2^(log_4(n)+1) - 2 = (assume base is 4): n*2^(log_4(n)+1)-2 - n*log(n) = n*4n-2-n*log(n) = 4n2-nlog(n)-2 <= 4n2 = O(n2)
(l) = n2*sum[to log_9(n)](27^i)((1/9)^2i) = n$2sum[to log_9(n)](27/81)^i = n2*sum[to log_9(n)](1/3)^i <= n2/2 = O(n2)

Anonymous

Anonymous Sat 28 Mar 2020 02:49:54 No.11507867 Report

Quoted By:

bruh we got the same coursework

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