Even three years later you can be proud your video is helping a random guy from the internet struggling to understand recurrence solutions. Thanks for posting it. 😊
at 8:53, instead of converting to 2 times the sum of numbers, you can convert it to k(k-1). This allows you to skip the entire summation substitution, and after finding k=n, you can get n^2 - n from that
Thanks for the insight. From my perspective the way Randerson presented the work flow was incredibly helpful. For someone who is new to this or hasn't had good instructors in the past, taking shortcuts too early makes things difficult. Showing an example of such an elementary summation gave me the intuition for future more complex problems. Thanks again for your comment on how to pick the low hanging fruit.
Wow thank you sooo mucchh 😭😭 Btw, just a question, will it be much better to use the 2(k-1+k-2+...+1) Than k(k-1) I tried guessing the pattern myself and my simpleton brain got T(n) = T(n-k) + k(2n) - (k(k-1)) instead, now I'm wondering if using the summation would be better?
if you define the a function f’(n) where f’(n) is the inverse of function f(n) you can subtract T(n-1) and then divide by 1 you will get f’(n) = O(n) if you take the anti derivative of this result you get f(n) = O(n^2)
So I have a factorization algorithm. It is a sieve. But it involves checking the sums of naturals greater than N (the number to be factored) for certain conditions. Because the sums of the natural numbers increase by the square and N increases linearly. Does that mean my algorithm is N P efficient? It works particularly well for numbers congruent to + or - 1 (mod 6) whose factors are roughly of equivalent magnitude ie. public key style security numbers. That is the sums necessary are likely in close proximity on the number line to N if N is relatively square (that is as far as its factors being similar magnitude). I do recreational thinking and am not a programmer. Certainly not with large integers in hex.🤪
Why does my prof suck so bad that this concept was so easily explained by you, a random dude on youtube (in the best way), and he couldn’t even tell us what k meant
From the definition of Big O, there must exist some constant c, such that c*n^2 >= n^2+n. And since n^2 is quadratic and n is linear, n has almost no effect on n^2 when n is very large. If you scale constant c large enough, you'll find a c where it satisfies the relation I stated earlier.
Even three years later you can be proud your video is helping a random guy from the internet struggling to understand recurrence solutions. Thanks for posting it. 😊
Four years and still helping another random guy lol
Here also from 2025😅😅
This is one of the best explanations, step-by-step, on how to solve recurrence equations using induction/back substitution. Fantastic job!!!
Bro this made so much more sense than the way I was taught. thank you so much!
Glad the video helped!
at 8:53, instead of converting to 2 times the sum of numbers, you can convert it to k(k-1). This allows you to skip the entire summation substitution, and after finding k=n, you can get n^2 - n from that
I’m going to try and understand that this weekend! Thanks for the tip.
Thanks for the insight. From my perspective the way Randerson presented the work flow was incredibly helpful. For someone who is new to this or hasn't had good instructors in the past, taking shortcuts too early makes things difficult. Showing an example of such an elementary summation gave me the intuition for future more complex problems. Thanks again for your comment on how to pick the low hanging fruit.
I really like the way you say alright, so calm and collected
much more sense than i from my class thanks a lot
You absolutely killed the explanation on this video!!! Great job!! and you have been an immense help! Super glad I found this video!!
Wow thank you sooo mucchh 😭😭
Btw, just a question, will it be much better to use the
2(k-1+k-2+...+1)
Than
k(k-1)
I tried guessing the pattern myself and my simpleton brain got T(n) = T(n-k) + k(2n) - (k(k-1)) instead, now I'm wondering if using the summation would be better?
if you define the a function f’(n) where f’(n) is the inverse of function f(n) you can subtract T(n-1) and then divide by 1 you will get f’(n) = O(n) if you take the anti derivative of this result you get f(n) = O(n^2)
This is phenomonel, thank you! Couldn't have asked for a better explaination.
When K = 3, why are you throwing in the non-T terms from the K = 2 iteration 2(2n)-2 instead of the non-T terms from the K = 1 iteration 2n?
Many thanks, is there anywhere to find more summation formulae you recommend?
Beautifully explained!! Thank u so so much. Never understood this til now🎉
Why at 11:20 he is doing T(n-k) = 0 ? and not T(n)
because that is the base case
In the last step, what happens to the 2n squared and the minus sign to get n squared plus n?
In the previous step the equation simplifies to:
2n^2 - n^2 + n
From there we get:
n^2 + n
@@randerson112358 I was screwing up on basic algebra. These videos are great.
So I have a factorization algorithm. It is a sieve. But it involves checking the sums of naturals greater than N (the number to be factored) for certain conditions. Because the sums of the natural numbers increase by the square and N increases linearly. Does that mean my algorithm is N P efficient? It works particularly well for numbers congruent to + or - 1 (mod 6) whose factors are roughly of equivalent magnitude ie. public key style security numbers. That is the sums necessary are likely in close proximity on the number line to N if N is relatively square (that is as far as its factors being similar magnitude). I do recreational thinking and am not a programmer. Certainly not with large integers in hex.🤪
Why does my prof suck so bad that this concept was so easily explained by you, a random dude on youtube (in the best way), and he couldn’t even tell us what k meant
finally a video that made me understand this concept!!!
an = an-1 + 2n a0 = 2 , solve the recurring relation. whats the solution for this ? like closed formula .
there is definitely a simpler way to do this, can't be asked to type it out but if this is how your prof wants u to do it doesn't matter
The title should be "How To Solve this one Recurrence Relation"
bro king of explanation keep the great work
Thanks for this amazing and fulfilling explanation... literally helped me a lot!
Sir. What about when it is k+1?
Why is it called O(n^2) instead of Teta(n^2)? The only part i didn't understand.
Thank you for the lecture. It helped me so much, u are the best
This made so much sense, great video
Thank U 🙏 Mr. Randerson🙌
Thanks so much, I was lost at first
How did you go from ( n^2 + n ) to conclude its O (n^2)? Why is it not O (n^2 + n) ?
Because n^2 larger than n then O(n^2) is enough
You can just take the largest degree of a polynomial
From the definition of Big O, there must exist some constant c, such that c*n^2 >= n^2+n. And since n^2 is quadratic and n is linear, n has almost no effect on n^2 when n is very large. If you scale constant c large enough, you'll find a c where it satisfies the relation I stated earlier.
thank you, untag makaanswer ko sa exam hahahha
BRO U ARE THE GOAT
I really like the way you explained this. Very helpful and easy to understand. Thank you so much for your time.
Thanks for watching!
thank u so much, this video was really helpfull. following from ALGERIA
Q.t(0)=2
t(n)=3t(n-1)+n+2^n
Thank you so much for your video, it really helped me out
Finally some material with American accent
This is really helpful video thanks Rand!
Thanks A LOT! you are a true life saver!
This is awesome!! Thank you my friend.
mannnnnnnnnnnn you're a real one bro!!!!!!!!!
Thanks! I appreciate it!
lifesaving video fr
Very helpful! Thank you!
Very clearly explained, thanks a bunch!
man you are my god
You are my hero! Thanka
thank god for this
amazing video, thanks so much!
Thanks you for watching Vanessa, I'm glad you liked it!
Excellent, thank you very much!!
great explaination, thanks!
Very well explanation thx bro, u r a savior
Great job! very informative
Thanks !
So helpful, thank you!!
Thanks Lexi, I appreciate it and I'm glad that the video was helpful.
Randerson thank you so much!
Thank you.
More easier method is Master theorem for decreasing function can be used instead.
can you expand on that please?
had to like and subscribe :)
Thank you!
Thanks bro
Very good 👍
Thank you !
This was so hard to follow
Really nice, thank you!
Amazing.
great video
Thanks, I appreciate that !
Literally save my ass lol
T(n) =0 if n= to what???? AND T(n)= T(n-1)+2n if n= TO WHAT????. Please give a fully equation for better understanding. Thanks
it says T(0) is 0 and T(n) for all other cases
Nice!
I appreciate the comment !
Thaks sir
I love you
Haha I appreciate that! Thanks for watching Java With Hawa.
damn, can not understand
ts fire
randerson112358 da goat
Uninentional asmr 😏😏😏
noice
What the fuck is he talking about?
Recurrence relation......
Volume a bit too low mate