How To Solve Recurrence Relations
Вставка
- Опубліковано 12 лип 2019
- ★Please Subscribe !
/ @randerson112358
★Easy Algorithm Analysis Tutorial:
www.udemy.com/algorithm-analy...
★Recurrence Relation Made Easy: www.udemy.com/recurrence-rela...
►Tree Traversal Videos:
(1) Preorder: • Preorder Traversal
(2) Postorder: • Postorder Traversal
(3) Inorder: • Inorder Traversal
(4) Tree Traversal Example: • Tree Traversal Example
►Videos on Discrete Math Induction:
(1) Induction Summation: • Proof By Induction Sum...
(2) Mathematical Induction Divisibility: • Proof By Induction Div...
(3) Induction Recurrence Relation 1: • Recurrence Relation Pr...
(4) Induction Recurrence Relation 2: • Recurrence Relation Ru...
►Videos on Logical Equivalence:
(0) Logical Equivalence: • Prove Logical Equivale...
(1) Tautology: • Truth Table Tautology ...
(2) Tautology: www.youtube.com/watch?v=okZcT...
(3) Contradiction: www.youtube.com/watch?v=YXSYB...
(4) Laws: • Laws Of Logical Equiva...
►Videos on Big-O Asymptotics:
(1)Solve Big O: • Solve Big-O By Definition
(2)Solve Theta: • Prove Big Theta
(3)Solve Big Omega: • Prove Big Omega
(4)Big O Notation Explained: • Big O Notation Explained
►Summation Videos:
Closed Form Solution Summation: • Closed Form Solution S...
Algorithm Analysis Summation: • Algorithm Analysis and...
Summation / Sigma Notation: • Summation / Sigma Nota...
Summation Closed Form Solution: • Summation Closed Form ...
Evaluate The Summation: • Evaluate The Summation
Time Complexity of Code using summations: • Time Complexity of Cod...
►Recurrence Relation Videos:
Recurrence Relation Proof by Induction: • Recurrence Relation Pr...
Recurrence Relation Run Time by Induction: • Recurrence Relation Ru...
Recurrence Tree: • Recursion Tree Method ...
►Big O, Big Omega, Big Theta Limit Videos:
(1) Solve Big Omega by Limits:
• Solve Big Omega By Limits
(2)Solve Big O by Limits:
• Solve Big-Oh By Limits
(3) Prove Little-o By Limits:
• Little o Proof Using L...
(4) Solve Big Theta By Limits:
• Solve Big Theta By Limits
♥ Visit My Website:
everythingcomputerscience.com/
♥Support this channel on Patreon:
/ randerson112358
♥Helpful Books:
►Algorithm Analysis Books:
www.amazon.com/gp/product/026...
►Discrete Mathematics Workbooks:
(1) Practice Problems In Discrete Mathematics - www.amazon.com/gp/product/013...
(2)Discrete Mathematics Workbook - www.amazon.com/gp/product/013...
#recurrencerelations #iterationmethod #recurrence relationiteration
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
This is one of the best explanations, step-by-step, on how to solve recurrence equations using induction/back substitution. Fantastic job!!!
finally a video that made me understand this concept!!!
Just got me from a 60 on this HW to a 100. Thank you sir.
@Bruce Khalil yup, I have been using flixzone} for years myself :D
i hope you failed later lol lol lol #funny
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.
This made so much sense, great video
bro king of explanation keep the great work
Beautifully explained!! Thank u so so much. Never understood this til now🎉
This is phenomonel, thank you! Couldn't have asked for a better explaination.
Thanks A LOT! you are a true life saver!
Many thanks, is there anywhere to find more summation formulae you recommend?
thank you, untag makaanswer ko sa exam hahahha
BRO U ARE THE GOAT
Thank U 🙏 Mr. Randerson🙌
Very clearly explained, thanks a bunch!
You absolutely killed the explanation on this video!!! Great job!! and you have been an immense help! Super glad I found this video!!
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.🤪
Thanks for this amazing and fulfilling explanation... literally helped me a lot!
thank god for this
Randerson thank you so much!
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)
an = an-1 + 2n a0 = 2 , solve the recurring relation. whats the solution for this ? like closed formula .
Excellent, thank you very much!!
You are my hero! Thanka
I really like the way you explained this. Very helpful and easy to understand. Thank you so much for your time.
Thanks for watching!
This is awesome!! Thank you my friend.
The title should be "How To Solve this one Recurrence Relation"
Sir. What about when it is k+1?
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?
Q.t(0)=2
t(n)=3t(n-1)+n+2^n
great explaination, thanks!
Thank you so much for your video, it really helped me out
mannnnnnnnnnnn you're a real one bro!!!!!!!!!
Thanks! I appreciate it!
This is really helpful video thanks Rand!
amazing video, thanks so much!
Thanks you for watching Vanessa, I'm glad you liked it!
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?
Great job! very informative
Thanks !
So helpful, thank you!!
Thanks Lexi, I appreciate it and I'm glad that the video was helpful.
man you are my god
Thank you.
Very well explanation thx bro, u r a savior
Really nice, thank you!
Thanks bro
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.
Thanks!!
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
Amazing.
Very good 👍
Thank you !
Thaks sir
Why is it called O(n^2) instead of Teta(n^2)? The only part i didn't understand.
had to like and subscribe :)
Thank you!
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.
Nice!
I appreciate the comment !
Why at 11:20 he is doing T(n-k) = 0 ? and not T(n)
because that is the base case
great video
Thanks, I appreciate that !
Finally some material with American accent
I love you
Haha I appreciate that! Thanks for watching Java With Hawa.
More easier method is Master theorem for decreasing function can be used instead.
can you expand on that please?
Literally save my ass lol
This was so hard to follow
randerson112358 da goat
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
noice
damn, can not understand
Uninentional asmr 😏😏😏
What the fuck is he talking about?
Recurrence relation......
Volume a bit too low mate