subject
Mathematics, 16.09.2019 16:10 st23pgardner

Master theorem: t(n) = 3t(n/3) + o(log n)? hello, i've been trying to solve the bounds for the recurrence stated in the title: i know a = 3, b = 3, and f(n) = o(log n), n^log(a) of base b --> n^log(3) of base 3 --> n^1 = n. so i get θ(n). now i proceed to use case 1 of master theorem: if f(n) = o(n^log(a-e) of base b) for some constant e > 0, then t(n) = θ(n^log(a) of base b) since f(n) < n^log(a) of base b, asymptotically. i believe the solution should be θ(n) but where i am stuck is proving that f(n) is polynomially smaller, when using case 1, the ratio of f(n) / n^log(a) of base b: = log n / n, so that the solution θ(n) is true any with this is appreciated

ansver
Answers: 1

Other questions on the subject: Mathematics

image
Mathematics, 21.06.2019 18:30, joejoefofana
What is the area of the triangle 10 13 12
Answers: 1
image
Mathematics, 21.06.2019 21:30, lexiiiee
Solve -.016x= -16. need solving this
Answers: 2
image
Mathematics, 21.06.2019 22:00, ash2905
Can you me find the slope! (30 points)
Answers: 2
image
Mathematics, 21.06.2019 23:10, alemorachis49
You just purchased two coins at a price of $670 each. because one of the coins is more collectible, you believe that its value will increase at a rate of 7.1 percent per year, while you believe the second coin will only increase at 6.5 percent per year. if you are correct, how much more will the first coin be worth in 15 years?
Answers: 2
You know the right answer?
Master theorem: t(n) = 3t(n/3) + o(log n)? hello, i've been trying to solve the bounds for the rec...

Questions in other subjects:

Konu
Mathematics, 28.04.2021 21:40