Algorithms - Solving Recurrence Relations By Substitution
Вставка
- Опубліковано 1 чер 2024
- Please support me on Patreon: / thesimpleengineer
/ thesimpengineer / schachte
ryan-schachte.com
Don't forget to subscribe! ➨ Website -
➨ New Video! - • Docker Client, Images ...
➨ / the-simple-engineer-80...
➨ Github - github.com/schachte
---------------------------------------------------------------
In this video I talk about what recurrence relations are and how to solve them using the substitution method. We analyze two popular recurrences and derive their respective time complexities. - Комедії
Thank you for your explanation of this technique. This is the first video about DSA that I could watch entirely without feeling boring. I hopefully you can make more videos about the techniques that are frequently used in interview problems.
What 5 websites, 3 other tutorial videos and my prof couldnt explain well enough for me to get, you have managed to explain perfectly clearly how to do this. Thank you.
This one video just clarified 4 weeks of confusion for me. Thank you so much!
Thank you so much.. I hadn't understood this for years and this one lecture changed it..
That was incredible. You explained this much better than my professors or the TAs ever did. Subscribed!
Thanks!
You've explained this better than any other video on youtube. Finally, I understand this stuff now.. Thanks for posting this
am gonna see depending ur comment
Thank you for making the video, you've explained it really well!
THANKS i almost cried all other algorithms explanation videos sucked so bad its like they want me to fail the course (bad instructor bad videos) but im saved by you yaaaaaaaaaaay
tried ***,,e5tbary bkrh ..pray for me
you can also checkout this one . Just too good ua-cam.com/video/Ob8SM0fz6p0/v-deo.html
Amazing presentation man. I wish my university professor was as clear as you were in the video. Kudos!
You made this very easy to understand, thank you!
Exactly what I was looking for. :-) Thanks.
Great video. Thank you so much.
Thanks for the explanation!!!!!!!!
Great explanation. thank you
you are the BEST, you solve the biggest problem for me in the woooooooorld
:)
Great video. Thanks.
Thank you Brother
you know there is a very high pitched screech in your into.
i noticed as well, because of the pain in my ears
I do like his tutorials but I always jump that Intro.
wow- that did it for me!
I found this video very helpful but there needs to be clarification at @12:52. The linear term, n*c, didn't fall from the sky. It comes from the 'merging' operation of elements from two sorted containers (each containing a subset of elements sorted from a more recent recursive call). The merging operation (a sorting algorithm in its own right, I suppose) involves comparing 2 elements at a time, one from each container, until either or both containers are exhausted. The larger (or smaller, depending on whether you sort high-low or low-high) of the two element is inserted into another container to be used in the next recursive step. The comparison and insertion constitute n*c complexity.
Also worth noting: 'k' represents how many levels 'deep'/'down' you are in your recursive call.
Category comedy, Nice :P
Loved the presentation. 😍 Which software do use to make such amazing stuff?
Thanks! I used a Wacom Intuous tablet for drawing, Camtasia for editing, Adobe Audition for the audio and After effects for the intro.
THANKS man
Very nice video.....understood it all. BTW which software do you use to write?
Sketchbook
18:00. Much simpler just to say 2^k = n as you already had that instead of doing the complicated log simplifying thing
In case of recurrences like T(n) = T(2n/3) + T(n/3), this method doesn’t work. What kind of methods could we then use?
@: in video, where did you get the 3rd C?
thanks for your excellent explanation , I have a question : I want to solve the recurrence relation T(n)=T(n−1)+O(n) for n>1, T(1)=1.
what is O(n)? is O(n) equals to constant or what?
There is a convention in macro substituion that states : "a set in a formula rep an anonymous function in set " so the O (n) represents a function h(n)
What is going on with the substitution of the 2t(n-2)+c how do you sub and get rid of all the terms like the T and the -1?
I see now, took a minute,
The time complexity of the first algorithm is NOT 2^N.
It is N: to obtain the tenth Fibonacci number you just need to compute the previous nine numbers. You definitely don't need 2^10 (one million) computations.
Without memoization you're recomputing values already seen I believe.
That's correct for the iterative implementation. For a recursive implementation, however, it takes exponential time as shown in the video because of repetitive computations. You can draw a recursion tree to see how the same values are computed multiple times which is why the recursive implementation is generally very slow for large n ( n>=30)
Why add the "+C" after the "2T(n-1)" when solving the recurrence of the Fibonacci?
I think it's a time taken for other stuff like the addition between T(n-1) and T(n-2) on fibonacci, CMIIW
These are great videos. Too bad they don’t show up in Google results and instead I get stuff from people who are better at SEO than SE.
I think I understand the concept, but I can't for the life of me solve them. do you guys have any advice?
Sir can you explain me what is log2(n)?
its actually log n with base 2
is the solution in explicit form??
I wish any of these steps made sense to me. Why are we guessing about upper bounds all of a sudden? What the hell??
how did you get n/2^k = 1 @ 16:47?
He says "I want to recurse to the base case, otherwise I'll have a never-ending algorithm". With this, we want T(n/2^k) to become T(1) [[The base case]].
T(n/2^k) must become T(1). Therefore, in the base case, n/2^k = 1
OH! Thankyou! :D
Considering integer division, n/2^k will reach 1 eventually.
08:04 wouldnt that 2^0 be 2^1?
I need help on solving this recurrence relation. I've been stuck on it. T(1)=5, T(2)=11, T(n)=5T(n-1)- 6T(n-2) PLEASE HELP
Convert it into a quadratic equation.
T(n) - 5T(n-1) + 6T(n-2) = 0
(t^2) - 5t + 6 = 0
t = 2, t = 3
T(n) = A(2^n) + B(3^n) [from solution to quadratic equation]
Now we use base condition
T(1) = 2A + 3B = 5
T(2) = 4A + 9B = 11
Solve for A and B. A = 2, B = 1/3
T(n) = 2(2^n) + (1/3)(3^n)
T(n) = 2^(n+1) + 3^(n-1)
This is the same as this and the same as that and the same as this.... bro what?
U took 1 ,1 ,2
So how can it be equal to n-2 ,n-1 ,n ????
Its a series . the n represents the positional value . if you take 2 to be in nth place the 1 is in n-1th place or if you take 1 as n the 2 is in n+1 th place . Simply we are indexing them based on 'n'
this could have been clearer. sorry but this didn't help. it was nice but you run off once you get into it
i think you have done this by iteration method and not by subsitution method. Subsitution method requires to take an initial guess , which ofcourse you havent taken here
Hashir Khalid I believe you are referring to non homogeneous linear recurrence relations
^sorry my mistake, i got it now ! BTW thanks for the lecture. Nicely poised and easily understandable
Hashir Khalid My pleasure! I made another lecture on non homogenous LRR's as well if you're curious.