burnt ermine
ATM im doing some practice qns for solving recursions and came across this qn
i got stuck so i looked at the provided answer which is this(image1), but they never show the working so i'm trying to figure that out.
I don't really understand how to derive epsilon at this point, so i put like my 3 guesses as to how to solve, just need liek a bit of guidance for this part
abstract nimbusBOT
ATM im doing some practice qns for solving recursions and came across this qn
...
+close
spring field
ATM im doing some practice qns for solving recursions and came across this qn
...
Hmm...
Let n = 4^k. Then:
T(4^k) - 3T(4^(k - 1)) = k 4^k ln(4)
Next, let a(k) = T(4^k). Then:
a(k) - 3a(k - 1) = k 4^k ln(4)
This is now a linear recurrence relation, which is easy to solve.
burnt ermine
damn
burnt ermine
Hmm...
Let n = 4^k. Then:
T(4^k) - 3T(4^(k - 1)) = k 4^k ln(4)
Next, let a(k) = ...
is this still using master theorem?
spring field
is this still using master theorem?
Don't know what that is.
burnt ermine
ah
one sec
need to solve using this
actually im sure ur method works as well, but i wanna learn how to make use of the master theorem to solve this (now that i know it is possible to do so)
spring field
Hm... While I somewhat understand it, I don't really have experience using it, so I likely won't be able to help with that.
burnt ermine
alls gd, thanks
spring field
I can tell you the exact solution of the recurrence, though.
spring field
Well, it's not like that's really going to help you with your approach.
burnt ermine
true
spring field
Anyway, the true solution is:
T(n) = Cn^log(4, 3) + 4n ln(n) - 12ln(4)n
Here C is an arbitrary constant.
Well, good luck with your approach!
If you can do it, can you share it? I'm interested in how it works.
burnt ermine
my lecture is trash
this sht is goated
basically just follow this and can get the answer
which is nlogn (same answer as in the answer sheet)
burnt ermine
Well, good luck with your approach!
If you can do it, can you share it? I'm inte...
^
burnt ermine
Anyway, the true solution is:
T(n) = Cn^log(4, 3) + 4n ln(n) - 12ln(4)n
Here C i...
yeah more or less this but simplified to nlogn (the goal is to find the theta (tight bound) value)
spring field
yeah more or less this but simplified to nlogn (the goal is to find the theta (t...
I'll take a look. Thanks for that!
My approach should also always work for T(n) = a T(n/b) + f(n). Basically, I reduce it to a linear recurrence, which is easy to solve. Well, easy as long as f(n) isn't too complicated, but linear recurrences are just easier to work with in general.
white ploverBOT
@spring field has given 1 rep to @burnt ermine
burnt ermine
Oh how do u rep