Recurrence Relation By Substitution
ฝัง
- เผยแพร่เมื่อ 3 ก.ย. 2014
- Recurrence Relations:
Solve a recurrence relation by substitution, also known as backwards substitution, iterative method, and iterative substitution.
www.udemy.com/recurrence-rela...
To see how 2(n -1) = O( n ) go to this video link:
• Solve Big-O By Definition
Please Subscribe !
-----------------------------------------------------------------------------------------------------------
►Tutorial:
www.udemy.com/recurrence-rela...
-----------------------------------------------------------------------------------------------------------
►Website: everythingcomputerscience.com/
-----------------------------------------------------------------------------------------------------------
►BOOKS:
**PROGRAMMING***
C-Programming - www.amazon.com/gp/product/013...
Head First Java - www.amazon.com/gp/product/059...
**DISCRETE STRUCTURES/MATHEMATICS**
Discrete Mathematics Workbook- www.amazon.com/gp/product/013...
Practice Problems In Discrete Mathematics -www.amazon.com/gp/product/013...
**ALGORITHMS**
Algorithm Analysis - www.amazon.com/gp/product/026...
---------------------------------------------------------------------------------------
Thanks a lot man! You explained in 8 Minutes what neither my prof nor hours of googling and reading books weren't able to explain to me. Great break down of the individual steps!
its a miracle
Holy crap you have no idea how grateful I am for this video. Bless your soul, you absolute legend.
awesome man, u r really great , i couldn't understand a word of what my lecturer taught, but u owned it man, thank you a lot man
Made it much clearer than my professor's slides, thanks!
first time i got that properly. thanks for the explanation :)
It's a correct way of defining this theorm!
Great explanation, now I get it!
Excellent explanation.
Wish I could've liked this 10x more. You saved me in this class!
I'm glad the video could help!
Thank u for the explaination..
Thank you good sir! you did a better job than my university prof!
Thank you for the wonderful explanation.
+Jay Suthar I am glad you like my explanation. Thanks for watching!
Great explanation, thanks!
Thanks Joseph !
thanks that helped me
Thank you soooo much. Waiting for other algorithm explanation videos :'))
thx chief
Thank you very much for the video. I still need your help in determining the base case for the recurrence relation.
Thank you!
+BecauseAmAGirl thank you for watching!
I love you man.
Thank you so much!!
+Alex Chalamova thank you !
I am still confused but best explanation so far of all videos I've seen. I'm confused of the part where you start subbing in k.
Good idea listing k on the side.
Man you are awesome.... All of your videos are really good and easy to understand ...:) Keep sharing such videos (Y)
+Grad Student thank you, your comments are to kind
There's a difference between Plug and Chug and Substitution method for solving recurrences... Anyway nice explanation! :)
If you could point out how to derive to the summation formula which you have used on 5:10, that would be great. Thanks!
Really nicely done. There is a question in the comments about whether this is called the Substitution or Iteration method. I think it's just a matter of terminology. This method is either referred to as Backward Substitution, since you are substituting back into the original equation and it's also referred to as Iteration, since you are essentially iterating the original function recursively. There is another method called Substitution which involves guessing the asymptotic performance of an algorithm and then using mathematical induction to prove it. Again, great video. Thanks for putting this together!
Thanks Ethan !
randerson112358 You're welcome. What would be really cool to see as a follow-on is solving a recurrence equation using the Change of Variable method. I've struggled with the examples I've seen thus far even though it seems like a relatively simple method.
is this the substitution method i read in book something about guessing the solution first then solving it by induction....
+Sumit Ahar hi,
There is another method called substitution that uses induction.
This substitution method here is also known as iteration method, iterative substitution, etc.
NICE video learn a lot . Can you do one for RecursionTree Method
Hi, I have question about the general form. So k is the level of the recursion tree that we are at, right? Don't we need to sum the work done over all k from 0 to log(n) to get the total work that is done? How come we just consider the case of the leaves, where k = log(n), and then use the work done only in that level as the final solution? Thanks.
thx
Thx for watching!
Thank you for your video! If I had T(n) = 2T(n -1) + 3 and T(0) =1, would the general form be T(n) = 2^n (n-n???) + some constants? I am not sure what the latter half would look like.
+Michelle C
T(n) = 2T(n -1) + 3 and T(0) =1
k=2, 2 [ 2T(n-2) +3] + 3 = 4T(n-2) + 6 + 3 = 4T(n-2) + 9
k=3, 4[2T(n-3) +3] + 9 = 8T(n-3) +12 + 9 = 8T(n-3) + 21
k=4, 8[2T(n-4) + 3] + 21 = 16T(n-4) + 24 + 21 = 16T(n-4) + 45
k=5, 16[2T(n-5)+ 3]+45 = 32T(n-5) + 48 +45 = 32T(n-5) + 93
General Form:
2^k T(n -k) + 3*(2^k - 1)
sir, please explain recurrence relation for the power of an element using divide and conquer
pow(x,n)
if(n==0)
return 1;
else if n%2==0
y=pow(x, n/2);
return y*y;
else
return x*pow(n-1);
Why did you replace 2ˆ(k+1) for 2 (2ˆk -1) in this step 6:43?
It was fine in the beginning , but by the end I was more confused than I was before I watched this video.
You were solving stuff without explanation
Hi which part did you get lost?
randerson112358 When you were explaining the general equation. I just lost it, you went too fast.
Now I dont trust on my knowledge AND my thinking abilities.
Not your fault though
I see, you should trust ur own knowledge! I hope I can help spread some light.
That video at the end has a few summation equations. If you just want to understand recurrence relation
Watch "Use iteration method to solve T(n)" on TH-cam
th-cam.com/video/TEzbkIggJfo/w-d-xo.html
I hope this helps
is this method also referred to as telescoping??
Please state the summation formula that you used in 4:59
Hi randerson,
You did great!, Awesome VDO and could you please explain this
T(n) = 2T(n/2) + Θ(n), for any n>1 and T(1) = Θ(1).
The run time complexity of T(n) = ?
Hi +Nattapong Phuntusil ,
Thank you very much. Now for your problem T(n) = 2T(n/2) + Θ(n), for any n>1 and T(1) = Θ(1).
For runtime, the Θ(n) tells us a function f(n) grows less than or equal to another function g(n) times some constant and f(n) grows greater than or equal to some function g(n) times some constant.
Written simply as :
f(n) = g(n) * C2.
See: th-cam.com/video/Vzqaz4MDGvc/w-d-xo.html
So in this case our g(n) = n, meaning
f(n) = n * C2.
So we can replace Θ(n) with n or any function in the form An + B , where A>= 1 and B>=0. Since Θ(n) is the set of all functions in the form f(n) = An + B.
Now Θ(1) tells us something similar to the above
f(n) = 1 * C2.
So we can replace Θ(1) with 1 or any other constant
Now let's rewrite the equation
Base Case: T(1) = Some Constant Number
Recurrence Case T(n) = 2T(n/2) + n, for any n> 1
Now let's solve, using the master theorem th-cam.com/video/i5kTZof1LRY/w-d-xo.html !
Master Theorem
T(n) = AT(n/B) + n^D
In this case A=2, B=2, D=1
If D = Log Base A of B then Θ(n^D log(n))
==> 1 = log base 2 of 2
==> 1 = 1
Therefore T(n) = Θ(n^1 log(n)) = Θ(n * log(n))
randerson112358
while true do
Many thank you +randerson112358
end
I don't think it is substitution method, it is Iteration method .
Correct it is also called iteration method, this method goes by many names including substitution.
thanks man.
@ 4:57 you mentioned the summation relation and then you convert it to (2^(k+1)-2) could you please give me more information how did you come up with such simplification. I know that sum(x^k) where k=0 to n is (x^n+1-1)/(x-1) but i really don't know how you came up with your simplification. thanks
I used the summation formula.
en.wikipedia.org/wiki/Summation
Search for "Some summations involving exponential terms"
The very first formula can be used for summation_of(2^i) from i=1 to k to equal:
= [(2^1) - (2^(k+1)) ]/[ 1 - 2 ]
= (2 - 2^(k+1)) / (-1)
= (-2^(k+1) + 2 ) / (-1)
= 2^(k+1) - 2
Thanks for watching;
randerson112358
thanks really useful explanation
Awesome video! Thanks for the help! :)
I was just wondering. Approximately at 6.00 you say that we want n = 1. You also say that this happens when T(n/2^k = 1). Why is that? Basically, I don't understand why n = 1 when (n/2^k = 1)
+Ihatenicknames1
Hi,
We want the base case to stop this recurrence, the base case is T(1) = 0
This only happens when n=1 such that T(n) = T(1) = 0
So we need this transformation from terms of k, to terms of n.
such that the base T(terms in k) = T(terms in n) = T(1) = 0
and
such that the recurrence is in terms of n
So we have our current situation where our recurrence is in terms of both k and n, we just want it in terms of n so we need to get rid of the k, or transform it in terms of n. This is out T(n/2^k)
In order for T(n/2^k) = T(1) = 0 , we need n/2^k = 1hence we need 2^k = n
Doing some algebra:
n/2^k = 1
==> n = 2^k
==> log2(n) = k
So now we can replace k with log2(n) for all k values in the recurrence and get our base case (STOPPING CASE) for the recurrence.
-randerson112358
+randerson112358 Thank you! You are helping me so much with my algorithm course.
Hey, great video! Why did you replace 2^log(n) for n @07:05?
Hi +Ronaldo Resende ,
Excellent question, I replaced 2^log(n) with n because,
1) I needed to know when the recurrence 'T(n)' will stop for the General Form.
2) The original recurrence is in terms of 'n'
I'll explain. The recurrence T(n) only stops for the base case T(1), so when n= 1.
In the general form which equals 2^k * T(n/2^k) +( 2^(k+1) - 2 ), we want to know when T(n/2^k) will stop, which again is when we have T(1). So this means that we need n/2^k = 1.
Doing some algebra we can solve for the equation n/2^k = 1.
==> n/2^k = 1
==> n = 2^k (by multiplying both sides by 2^k)
==> log( n )= k (this is log base 2 of n)
So this means that we can replace k with log n so that our T(n/2^k) function will become T(1), and all of the other k values in the general form will now be in terms of n.
For example: General Form = 2^k * T(n/2^k) +( 2^(k+1) - 2 )
= 2^log(n) * T(1) + (2^(log(n) + 1) - 2)
==> Notice all values of k are now in terms of n, and we have our base case T(1).
I hope that helps and thanks for watching the video !
randerson112358
+randerson112358 Lets say if we were to make the function become T(2)? how to proceed
Like any other function replace n with 2
T(n) = 2 * T(n/2) + 2, T(1) = 0
So now n =2 to get,
T(2) = 2 * T(2/2) + 2, T(1) = 0
==> 2 * T(1) + 2, T(1) = 0
==> 2 * 0 + 2 = 2
--OR--
You can use the general solution from the video that we solved for by getting rid of the recursion.
T(n) = 2(n -1)
So now n=2 to get,
T(2) = 2(2 -1) = 2
Hey, I really liked your videos on recurrence! Very well structured and easy to understand and to follow along. However, what would the solution be for T(n) = 3T(n/3) + n^3 T(1) = O(1) using the same methode? I'm really struggling with this. Please help!
+Anecxina
Hi, for recurrence relation in that form use the "Master Theorem".
I have a video on that here: th-cam.com/video/i5kTZof1LRY/w-d-xo.html
I hope this helps !
Thanks for watching
randerson112358
Thank you for replying.
I have already thought about using the Master Theorem on it because that's all I could find online.
However, at university they want us to solve it with this Iteration Method. Is this even possible?
+Anecxina I see, yes this is possible using the iteration technique.
I will see if I have time to make a video on this later.
Here you go:
th-cam.com/video/lkQWde4ZCC0/w-d-xo.html
Thank you very much!! :)
if there is a constant in front of the T function that can be simplified in the terms of two like T(n)=7T(n/2) what should i do in this question not n is a power of 2 and T(1)=1 and this video is really helpful thanks ^_^
Thanks, below is the answer to your question.
Iteration 0 "Base Case"
T(1)= 1
---------Iteration k=1------------
T(n)=7T(n/2) = 7^1 * T(n/2^1)
So we need to know what T(n/2) equals by using the T(n)= 7T(n/2) definition.
* T(n/2) = 7T((n/2) /2) = T(n/4)
--------Now we plug it back into the original equation-------
Iteration k=2
T(n) = 7*7*T(n/4) = 7^2 * T(n/4) = 7^2 * T(n/2^2)
So we need to know what T(n/4) equals by using the T(n)= 7T(n/4) definition.
* T(n/4) = 7T((n/4) /2) = 7T(n/8) = 7^3 * T(n/2^3)
--------Now we plug it back into the original equation--------
Iteration k=3
T(n) = 7*7*7*T(n/8) = 7^3 * T(n/8)
Now we can see pattern, and come up with a general form.
T(n)= 7^k * T(n/2^k)
Now we need to get k in terms of n using the base case, and get rid of the T(n/2^k)
T(n/2^k = 1) = 1,
This implies we need n/2^k to equal 1 so that T = 1
n/2^k =1 ===>>> n = 2^k ===>>> log n = k
Substitute log n with base 2 back into the general equation:
NOTE: log n is short for log base 2 of n.
T(n) = 7^k * T(n/2^k) ===>>> 7^(log n) * T(n/2^(log n))
==>> 7^(log n) * T(n/n)
==>> 7^(log n) * T(1)
==>> 7^(log n) * 1
==>> 7^(log n) > n^(log 7) = n^(2.807354....)
So this is O(n^(log 7))
You can also use the Master Theorem using this video to prove this, just note that d = 0 in this case.
th-cam.com/video/i5kTZof1LRY/w-d-xo.html
In 7:05, why is the whole term equals to n?
T(1)=0 is that suppose to be given in the question?
Yes, it represents the base case of the recursion (when it stops recursing).
How can we find value of T(0) and T(1) from the equation?
In the video I have here, the base case was given that T(1) = 0.
If the program or function or algorithm's base case is T(0) and T(1) then you know that they both equate to some constant amount of time.
That is:
T(0) = C1
T(1) = C2
Maybe these 2 video can help:
Function to Recurrence relation
th-cam.com/video/oh2yx701n9s/w-d-xo.html
and
Solving it:
th-cam.com/video/TEzbkIggJfo/w-d-xo.html
Thanks for watching;
randerson112358
what formula did you use at 4:54
+Joshua Veal I used summation formulas.
why is the answer O(n logn ) by master theorem?
please can you use a recursion tree to find the upper bound
Hi Obose,
Yes it is possible to find the upper bound using a recursion tree, the link to the video below should help you with that.
th-cam.com/video/vQt6ryhkYI0/w-d-xo.html
Another question what if we applied master theorem is it going to be the case 2 which is d=1=log2(2) and then we should get (n^d)logn =nlogn
I feel that my argument is not correct somehow and obvious it gives me a different solution than yours.
If you were to use the Master Theorem: th-cam.com/video/T68vN1FNY4o/w-d-xo.html
Then for the recurrence 2T(n/2) + 2, it would have to be in the form of the Master Theorem. AT(n/B) + Theta(n^D), which it is.
A=2, B=2, D= 0,
Solving for D is kind of tricky and for this you must understand what it means for a function to belong to Theta.
The number '2' is a constant function e.g. f(n) = 2 on a graph would give you a constand horizontal line. All constant functions belong to Theta(1).
So in this case Theta(n^D) = Theta(1) , so D must equal 0 as n^0 = 1.
So we use case 3, logB(A) > D, so f(n) belongs to Theta(n^ (logB(A)))
So log2(2) > 0 == 1 > 0 , so f(n) belongs to Theta(n^1)
Thanks for watching;
randerson112358
oh man this is amazing and awesome explanation really helpful and thanks from my heart
kind Sir why did you use n/2 for substitution
Hi,
I only substituted n/2 for n once.
Here is another example. T(n) = T(n/3) + 1, T(1) = 0
Iteration 1
T(n) = T(n/3) + 1
So we need to figure out what T(n/3) equals, we can do this by substituting n/3 for n to give us T( n/3 ) = T( (n/3) / 3) + 1 = T(n/9) + 1, notice I substitute n for n/3
So now during our 2nd iteration we get
Iteration 2
T(n) = T(n/3) + 1 = T(n/9) + 1 + 1 = T(n/9) + 2
Now we want to figure out what T(n/9) equals, we can do this by substituting n/9 for n to get
T(n/9) = T( (n/9) / 3) + 1 = T(n/27) + 1, notice I substitute n for n/9
So now during our 3rd iteration we get
Iteration 3
T(n) = T(n/27) + 1 + 2 = T(n/27) + 3
You can stop when you start seeing a pattern, and get a more general form,
let k = the iteration number
General Form in terms of k is T(n) = T(n/3^k) + k, T(1) = 0
So we want T(n/3^k) = T(1), which is the stopping point also known as the base case.
By doing some algebra we get
n/3^k = 1
n = 3^k
log n = k , where log n = log base 3 of n.
Substitute log n for k in the general equation to put the equation back in terms of n and get,
T(n) = T(n/3^k) + k = T(n) = T(n/3^(log n)) + log n = T(n/n) + log n = T(1) + log n
= 0 + log n = log n
So this is O(log n)
Let me know if you need me to explain more.
I hope this helps and thanks for watching my video :)
is iterative and substitution methods are same?
+Diwakar Shukla yes , and there is another method for solving recurrence relation called substitution method as well that is different.
+randerson112358 ,same and different ???it's confusing?
+Diwakar Shukla yes 2 different methods called substitution 1 is the same as iteration the other is different.
Iteration method has many different names for the same method.
aswome
Kind Sir sorry for this stupid question but why you say at the end of the video big o belongs to t of n?
At the end of the video I am showing the running time of the recurrence relation 'T(n)'.
I am saying that T(n) which equals 2* T(n/2) + 2 belongs to O(n).
Remember O(n) is just a set of functions, and the definition is that a function in this case T(n) is said to belong to O(n) if T(n) grows = some k value.
SO by me saying T(n) belongs to O(n) I am saying T(n) grows less than or eual to some other function like 10000*n whenever n>= 1.
I hope this helped some.
thank you
Kind Sir do you teach or tutor?
Hi, yes I do sometimes.
yes
Why always we define T ( 1) = 0 ?
+Nil Rojas Vales
You can define the base case as any constant you want. I usually choose 1 or 0 because it seems to make solving the equation easier
+Nil Rojas Vales
You can define the base case as any constant you want. I usually choose 1 or 0 because it seems to make solving the equation easier
Could you upload a video with the method "Recursion tree"?
It is quite confusing to me
boss
i want my lecturer replaced with this guy
how to solve following recurrence:
T(n)= T(n/2)+T(n/4)+T(n/8)+n
please give the solution.
1 6 6 6 XD
I think that 8+4+2=2^(k)-2, not 2^(k+1)-2, I 'm right? c:, sorry my bad english, is not my native lenguage.
No, when k=3 the equation is
T(n) = 8T(n/8) + 8 + 4 + 2, remember k=3
= 8T(n/8) + 14
= 8T(n/8) + 2^(3 +1) -2 , notice we plug in 3 for k for 2^(k+1)-2
I think the way you use should be iteration instead of substitution .
+Gan Xu hi, this method of solving recurrence relation has many different names (substitution, iteration, iterative substitution, etc.)
man wtf ! how the bigO is =n
you are Divided on 2 every time so the bigO is logn
Just because I am dividing by 2 every time doesn't make this recurrence log (n).
If you don't trust the proof in the video, you can do one of two things
1) Show me where my proof is wrong
2) Prove that this recurrence is log (n)
Thanks for watching, please if you do see something wrong with the proof, or have a proof that shows it's log(n) please comment on here so that everyone can see. However, although it is possible that I made a small mistake in the proof (which I've looked over countless times). The answer to the proof is definitely not log(n) and is O(n). If you can prove otherwise, I will be glad to post that correction, if you find that this proof is correct please comment to help others with this confusion.
Thanks Again;
randerson112358
i'm sorry I did not mean to insult but that what the doctor say to me that when we Divided on 2 the running time will be log(n)
....
can u show me when we will have log(n) ?
i have exam tomorrow please help me :( ... ?
This is a video, on the Master Theorem/Method
Hopefully this video will help !
th-cam.com/video/T68vN1FNY4o/w-d-xo.html
this is not substitution method it is iteration method.
How do you figure it's not substitution ?
You LITERALLY substitute n/2 for n in every "iteration".
What do you think the difference is between substitution and iteration is to solve a recurrence relation?
I would actually like to know if I am wrong, that way I can correct the video title and myself.
I believe another name for this method is "Iterative Substitution Method".
Agustin Sacco Yeah, you idiot!
this is iteration method not substitution...!!!
+M.Shoaib Omer yes this is substitution method also called iteration method .
I think you are referring to another method also called substitution
There are many different names for the same technique such as backwards substitution, iterative method, and iterative substitution.
Thanks for watching
Randerson112358
i think you made a mistake at min 2:28 isnt it supposed to be t(n/4)=2*t((n/4)/4)+2
or does the substitution happen at the main equation #1?
+yazan Hussein, yes the substitution happens for the main equation
T(n) = 2 * T(n/2) + 2.
+randerson112358 thank you very much so helpful, but i still find it hard analyZing functions like T(n-1), can you solve some in a video ?
Could you write out the problem please, and then hopefully I can make a video on it.
Fibonacci which i think is T(n-1)+T(n-2) but if you can work the recurrence relation too that would be amazing!! Thank you again for your amazing videos