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!
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 ruclips.net/video/Ob8SM0fz6p0/видео.html
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!
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
:)
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.
Thanks for the explanation!!!!!!!!
Thank you for making the video, you've explained it really well!
You made this very easy to understand, thank you!
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?
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.
18:00. Much simpler just to say 2^k = n as you already had that instead of doing the complicated log simplifying thing
Exactly what I was looking for. :-) Thanks.
Great explanation. thank you
Category comedy, Nice :P
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)
Great video. Thank you so much.
I think I understand the concept, but I can't for the life of me solve them. do you guys have any advice?
Thank you Brother
Great video. Thanks.
wow- that did it for me!
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)
I wish any of these steps made sense to me. Why are we guessing about upper bounds all of a sudden? What the hell??
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,
Very nice video.....understood it all. BTW which software do you use to write?
Sketchbook
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.
@: in video, where did you get the 3rd C?
THANKS man
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
08:04 wouldnt that 2^0 be 2^1?
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.
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'
Sir can you explain me what is log2(n)?
its actually log n with base 2
This is the same as this and the same as that and the same as this.... bro what?
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.