How To Solve Recurrence Relations

Подписаться 19 тыс.

Просмотров 161 тыс.

50% 1

★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

Опубликовано:

12 июл 2019

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 90

@MemoryException Год назад

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. 😊

@abdulwahabibrahimumar1308 2 месяца назад

Four years and still helping another random guy lol

@sergiocobo6000 5 месяцев назад

This is one of the best explanations, step-by-step, on how to solve recurrence equations using induction/back substitution. Fantastic job!!!

@themysteriousfox3767 18 дней назад

This is phenomonel, thank you! Couldn't have asked for a better explaination.

@ryujiyamasaki355 Год назад

finally a video that made me understand this concept!!!

@RobinD0903 Год назад

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

@MemoryException Год назад

I’m going to try and understand that this weekend! Thanks for the tip.

@jamesbowen9347 10 месяцев назад

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.

@reelwon3595 4 года назад

Just got me from a 60 on this HW to a 100. Thank you sir.

@bransonkody3416 3 года назад

@Bruce Khalil yup, I have been using flixzone} for years myself :D

@caseikelenboom2921 Год назад

i hope you failed later lol lol lol #funny

@Ali-up6sd 3 месяца назад

Beautifully explained!! Thank u so so much. Never understood this til now🎉

@nped5054 2 года назад

This made so much sense, great video

@awful999 2 месяца назад

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)

@FlawlessYT66 Год назад

bro king of explanation keep the great work

@ranad2037 2 года назад

Thanks A LOT! you are a true life saver!

@jellybean7613 Месяц назад

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?

@Traffy_01 2 года назад

Many thanks, is there anywhere to find more summation formulae you recommend?

@edinaleckovic2269 Год назад

You absolutely killed the explanation on this video!!! Great job!! and you have been an immense help! Super glad I found this video!!

@jayannamorsolo796 3 года назад

thank you, untag makaanswer ko sa exam hahahha

@davidshechtman4746 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.🤪

@manyhamy6330 Год назад

The title should be "How To Solve this one Recurrence Relation"

@Mohammed-hg6kw 4 месяца назад

Thanks for this amazing and fulfilling explanation... literally helped me a lot!

@PaulBoldyrev 2 года назад

Very clearly explained, thanks a bunch!

@luwluwstarshyne 7 месяцев назад

Thank U 🙏 Mr. Randerson🙌

@mdrsoooow Год назад

BRO U ARE THE GOAT

@trestenpool9045 3 года назад

Excellent, thank you very much!!

@antwanwimberly1729 2 месяца назад

This is awesome!! Thank you my friend.

@monicaj3878 3 года назад

Randerson thank you so much!

@naifabdullah3465 Год назад

I really like the way you explained this. Very helpful and easy to understand. Thank you so much for your time.

@randerson112358 Год назад

Thanks for watching!

@kylemauter5468 4 года назад

thank god for this

@Eutropios 7 месяцев назад

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?

@digantamondal2397 4 года назад

Q.t(0)=2 t(n)=3t(n-1)+n+2^n

@youtrip1037 3 года назад

an = an-1 + 2n a0 = 2 , solve the recurring relation. whats the solution for this ? like closed formula .

@pouyahallaj4445 2 года назад

You are my hero! Thanka

@DigvijaySingh-zd9hq 4 месяца назад

This is really helpful video thanks Rand!

@ilyasilyas6252 2 года назад

mannnnnnnnnnnn you're a real one bro!!!!!!!!!

@randerson112358 2 года назад

Thanks! I appreciate it!

@bestmovies939 3 года назад

Sir. What about when it is k+1?

@linpa Год назад

great explaination, thanks!

@taelocalxo4264 2 года назад

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

@vanessachow7313 3 года назад

amazing video, thanks so much!

@randerson112358 3 года назад

Thanks you for watching Vanessa, I'm glad you liked it!

@lexikelsall3114 3 года назад

So helpful, thank you!!

@randerson112358 3 года назад

Thanks Lexi, I appreciate it and I'm glad that the video was helpful.

@bilalbayrakdar7100 3 года назад

Very well explanation thx bro, u r a savior

@Aaron_Nie Год назад

man you are my god

@craigspencer2826 4 года назад

Great job! very informative

@randerson112358 4 года назад

Thanks !

@jfnwenflkwn 2 месяца назад

Thanks!!

@Matthew-dd6kp 11 месяцев назад

Thank you.

@MemoryException Год назад

In the last step, what happens to the 2n squared and the minus sign to get n squared plus n?

@randerson112358 Год назад

In the previous step the equation simplifies to: 2n^2 - n^2 + n From there we get: n^2 + n

@MemoryException Год назад

@@randerson112358 I was screwing up on basic algebra. These videos are great.

@Festival-sb2kf Год назад

Really nice, thank you!

@adarozer 2 года назад

Thanks bro

@Furkan-yv5ew 4 месяца назад

Why is it called O(n^2) instead of Teta(n^2)? The only part i didn't understand.

@Adam-xn9lt Год назад

Amazing.

@bestmovies939 3 года назад

Thaks sir

@blacksurface7995 4 года назад

Very good 👍

@randerson112358 4 года назад

Thank you !

@ilyasilyas6252 2 года назад

had to like and subscribe :)

@randerson112358 2 года назад

Thank you!

@enricodalpos5039 2 года назад

Why at 11:20 he is doing T(n-k) = 0 ? and not T(n)

@JoseWaldier 2 года назад

because that is the base case

@momoshikioot9177 3 года назад

How did you go from ( n^2 + n ) to conclude its O (n^2)? Why is it not O (n^2 + n) ?

@giahuyhoang8722 3 года назад

Because n^2 larger than n then O(n^2) is enough

@kgkcStudios 3 года назад

You can just take the largest degree of a polynomial

@42war_pig31 3 года назад

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.