Algorithms - Solving Recurrence Relations By Substitution

[@khanhchung5207]

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.

[@zetrox1870]

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.

[@rohanwadhavkar5343]

That was incredible. You explained this much better than my professors or the TAs ever did. Subscribed!

[@TheSimpleEngineer]

Thanks!

[@christianremwood4817]

This one video just clarified 4 weeks of confusion for me. Thank you so much!

[@Amande3p25]

You've explained this better than any other video on youtube. Finally, I understand this stuff now.. Thanks for posting this

[@onesimusambaw373]

am gonna see depending ur comment

[@شوقالرجيعي]

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

[@abdulwahedmm]

tried ***,,e5tbary bkrh ..pray for me

[@susantasharma]

you can also checkout this one . Just too good kzbin.info/www/bejne/hZObhIBmm99pppI

[@amruthsar]

Thank you so much.. I hadn't understood this for years and this one lecture changed it..

[@brianstorm597]

Amazing presentation man. I wish my university professor was as clear as you were in the video. Kudos!

[@adhwaaalanazi2552]

you are the BEST, you solve the biggest problem for me in the woooooooorld

[@TheSimpleEngineer]

:)

[@IsaacC20]

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.

[@IsaacC20]

Also worth noting: 'k' represents how many levels 'deep'/'down' you are in your recursive call.

[@Tylermania66]

you know there is a very high pitched screech in your into.

[@phoenixhartmann7121]

i noticed as well, because of the pain in my ears

[@giliza]

I do like his tutorials but I always jump that Intro.

[@riczd]

Thanks for the explanation!!!!!!!!

[@Furighteous]

You made this very easy to understand, thank you!

[@JinayShah]

Thank you for making the video, you've explained it really well!

[@udenithakshila2069]

Great explanation. thank you

[@janssenkuhn4049]

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.

[@DebasishOpu]

Great video. Thank you so much.

[@millermeares6676]

18:00. Much simpler just to say 2^k = n as you already had that instead of doing the complicated log simplifying thing

[@bulbul6]

Loved the presentation. 😍 Which software do use to make such amazing stuff?

[@TheSimpleEngineer]

Thanks! I used a Wacom Intuous tablet for drawing, Camtasia for editing, Adobe Audition for the audio and After effects for the intro.

[@rajdevlive]

Exactly what I was looking for. :-) Thanks.

[@malinayani]

Category comedy, Nice :P

[@jamesbones1668]

wow- that did it for me!

[@Joemakatozi1776]

Great video. Thanks.

[@fleal]

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?

[@icosmini]

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.

[@xXxOmarSanchezxXx]

Without memoization you're recomputing values already seen I believe.

[@srijaljoshi3421]

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)

[@drwhackadoodle360]

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?

[@drwhackadoodle360]

I see now, took a minute,

[@gaurav22221]

Thank you Brother

[@SmokyBigSmoke]

THANKS man

[@eXtrem1s]

Very nice video.....understood it all. BTW which software do you use to write?

[@TheSimpleEngineer]

Sketchbook

[@Lucas-ns9hd]

I wish any of these steps made sense to me. Why are we guessing about upper bounds all of a sudden? What the hell??

[@preet9343]

I think I understand the concept, but I can't for the life of me solve them. do you guys have any advice?

[@zainabmostafa7998]

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?

[@comcrasher]

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)

[@johnniegilkerson4724]

@: in video, where did you get the 3rd C?

[@hades2504]

is the solution in explicit form??

[@Kellworkie]

Why add the "+C" after the "2T(n-1)" when solving the recurrence of the Fibonacci?

[@Victim_Crasher]

I think it's a time taken for other stuff like the addition between T(n-1) and T(n-2) on fibonacci, CMIIW

[@aladdin_mck]

This is the same as this and the same as that and the same as this.... bro what?

[@shakeelrajput5038]

Sir can you explain me what is log2(n)?

[@comcrasher]

its actually log n with base 2

[@dancerham]

how did you get n/2^k = 1 @ 16:47?

[@EbenTuff]

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

[@dancerham]

OH! Thankyou! :D

[@amirtv106]

Considering integer division, n/2^k will reach 1 eventually.

[@LordShish]

08:04 wouldnt that 2^0 be 2^1?

[@toriacasta9308]

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

[@TarunMohandas]

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)

[@akshitarawat1970]

U took 1 ,1 ,2 So how can it be equal to n-2 ,n-1 ,n ????

[@comcrasher]

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'

[@delavago5379]

this could have been clearer. sorry but this didn't help. it was nice but you run off once you get into it

[@hashirkhalid2151]

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

[@TheSimpleEngineer]

Hashir Khalid I believe you are referring to non homogeneous linear recurrence relations

[@hashirkhalid2151]

^sorry my mistake, i got it now ! BTW thanks for the lecture. Nicely poised and easily understandable

[@TheSimpleEngineer]

Hashir Khalid My pleasure! I made another lecture on non homogenous LRR's as well if you're curious.