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.
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
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.
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.
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)
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)
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
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'
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)
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
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.
That was incredible. You explained this much better than my professors or the TAs ever did. Subscribed!
Thanks!
This one video just clarified 4 weeks of confusion for me. Thank you so much!
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 so much.. I hadn't understood this for years and this one lecture changed it..
Amazing presentation man. I wish my university professor was as clear as you were in the video. Kudos!
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 th-cam.com/video/Ob8SM0fz6p0/w-d-xo.html
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.
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.
you are the BEST, you solve the biggest problem for me in the woooooooorld
:)
18:00. Much simpler just to say 2^k = n as you already had that instead of doing the complicated log simplifying thing
You made this very easy to understand, thank you!
Thank you for making the video, you've explained it really well!
Thanks for the explanation!!!!!!!!
Great explanation. thank you
Great video. Thank you so much.
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?
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)
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.
Thank you Brother
Exactly what I was looking for. :-) Thanks.
08:04 wouldnt that 2^0 be 2^1?
Very nice video.....understood it all. BTW which software do you use to write?
Sketchbook
This is the same as this and the same as that and the same as this.... bro what?
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)
wow- that did it for me!
I wish any of these steps made sense to me. Why are we guessing about upper bounds all of a sudden? What the hell??
Category comedy, Nice :P
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,
is the solution in explicit form??
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
Great video. Thanks.
I think I understand the concept, but I can't for the life of me solve them. do you guys have any advice?
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.
Sir can you explain me what is log2(n)?
its actually log n with base 2
@: in video, where did you get the 3rd C?
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.
THANKS man
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'
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 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.