L-2.3: Recurrence Relation [ T(n)= n*T(n-1) ] | Substitution Method | Algorithm
ฝัง
- เผยแพร่เมื่อ 2 ต.ค. 2024
- #substitutionMethod#solveRecurrenceRelation#algorithm
👉Subscribe to our new channel: / @varunainashots
►Design and Analysis of algorithms (DAA) (Complete Playlist):
• Design and Analysis of...
Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
► Operating System :
• Operating System (Comp...
►Database Management System:
• DBMS (Database Managem...
► Theory of Computation
• TOC(Theory of Computat...
►Artificial Intelligence:
• Artificial Intelligenc...
►Computer Networks (Complete Playlist):
• Computer Networks (Com...
►Computer Architecture (Complete Playlist):
• Computer Organization ...
►Structured Query Language (SQL):
• Structured Query Langu...
►Discrete Mathematics:
• Discrete Mathematics
►Compiler Design:
• Compiler Design (Compl...
►Number System:
• Number system
►Cloud Computing & BIG Data:
• Cloud Computing & BIG ...
►Software Engineering:
• Software Engineering
►Data Structure:
• Data Structure
►Graph Theory:
• Graph Theory
►Programming in C:
• C Programming
►Digital Logic:
• Digital Logic (Complet...
---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
► Subscribe to us on TH-cam: / gatesmashers
►Subscribe to our new channel: / @varunainashots
► Like our page on Facebook: / gatesmashers
► Follow us on Instagram: / gate.smashers
► Follow us on Instagram: / varunainashots
► Follow us on Telegram: t.me/gatesmash...
► Follow us on Threads: www.threads.ne...
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:
Email us at: gatesmashers2018@gmail.com
![L-2.4: Recurrence Relation [ T(n)= 2T(n/2) +n] | Substitution Method | Algorithm](http://i.ytimg.com/vi/VHGisohk3Ck/mqdefault.jpg)
![L-2.4: Recurrence Relation [ T(n)= 2T(n/2) +n] | Substitution Method | Algorithm](/img/tr.png)
![L-2.6: Recurrence Relation [ T(n)= 8T(n/2) + n^2 ] | Master Theorem | Example#1 | Algorithm](http://i.ytimg.com/vi/FBKjvXGGCJM/mqdefault.jpg)
Sir at last the value of n.(n-1).(n-2)............3.2.1 can be O(n!)
Can't we write this as our answer???
Thanks a lot sir... Love your tutorials. May god bless you :) Thanks for being so good :)
Solution of given recurrence relation is n!. But its time complexity is O(n^n). See in worst case we take upper bound (i.e highest possible value for given function ). So we have to find upper bound For n! . If we expand it, it will give us n number of values n times (i.e n(n-1)(n-2).... or factorial of 5 will gives us 5 values 5*4*3*2*1). We also know that while finding O(c) we take it as O(1). So, to summarize O(n!) => O(n*(n-1) * (n-2)....1) => O(n*n*n...n) => O(n^n)
yeah i also got n!. So if question came in exam and both the options are present, should we go for n! or n^n?
@@jigz3903 same qsn..
Wrong. Review what big O represents. If the solution to recurrence is n! then the bound is c*n! because we can find some constant c that will always upper bound n! for some n>n0. While technically true that O(n!) is in the subset of O(n^n) we are trying to make the bounds as tight as possible in these problems. So saying O(n!) = O(n^n) doesn't really provide any useful insight about the algorithm. The solution to this recurrence is O(n!)
@@damianlarocque4958 you sure ?
I understand the reasoning provided, but there seems to be a misunderstanding in the interpretation. The time complexity of solving a recurrence relation involving factorials is indeed �(�!)O(n!) and not �(��)O(nn).
While it's true that �!n! can be expressed as �⋅(�−1)⋅(�−2)⋅…⋅3⋅2⋅1n⋅(n−1)⋅(n−2)⋅…⋅3⋅2⋅1, the growth rate of �!
Sir, shouldn't it be O(n!).
Can you please explain how we can say that O(n^n) is the answer?
Is there any role of asymptotic notations here?
Try to expand n! and you'll find n number of n's, and just multiply them
n! is the "answer" of the function whereas n^n is "time" taken by that function. If you want to find f(5), you will get 120 which is n! , on the other hand O(5^5) will be 3125 which is time taken by algorithm to solve problem. And this is the reason you should use "for loop" to find factorial of number which will give you answer in O(n) "time" but not O(n^n)
@@aayushjariwala6256 That's incorrect. The recurrence describes the function in terms of its value on smaller input which tells us the run time of the algo. The algorithm for finding the factorial of a number recursively is actually very simple and is O(n). The algorithm in this problem runs in O(n!)
As usual crystal clear explanation ❤
Finally i found perfect lecture for that topic.
Thanku sir🎉
Sir, can't we say time complexity of N factorial?! In this case!?
Yes, we can but the answer will remain same only [O(n*n)].
@@koushikkanumuri253 how
@@thedemonlord300 he had taken 'n' common in last but one line . If you observe it clearly it's n! . The time complexity of n! Is [O(n*n)]
@@koushikkanumuri253 What are you trying to say? The time complexity of an algorithm which runs in n! ...is well, O(n!)
@@koushikkanumuri253 for n! It will be O(n power n) order
Sir, Can we write it as O(n!) ?
yes
Dude.......n*(n-1)*(n-2)*........1 = n!
But not n^n🤦♂️🤦♂️🤦♂️🤦♂️
You make this subject easy for me... Thanks
this is the iterative method to solve the recurrence relation
Teachers in College🤡 Teachers in TH-cam(especially this sir👆)👑🙌🔥
Not insulting my college teachers, but just speaking up the fact..
Sir, you are teaching just phenomenal, I lost hope of learning DAA, but watching you, made me again interested in the Subject🔥🙌
Keep on making more such videos...❤
His teaching way is too better than anyone as well as he's handsome too👀💖
I was confused till I landed on your video. Thnx
sir aap bohat acha parhate hain please pakistan me ajayn karachi wali fast university me akr sary subjects parha den
Hahaha
Isme k times kyu nahi lia is problem mai ??? Can anyone explain ?
bhai tuze pata chala kya , kyu kiya tha n-1 , k ki jagah
Thanks 😊
Galat Bana Hai !!!
n*(n-1)*(n-2)*........................3*2*1 = n!
n*n*n*n*n*n*n*.............nth = n^n
salute to bro
Sir if we consider the term N then n*(N-1)*(N-2)(N-3)*..................................................*(N-N) *T(N-(N-1)) ............. does (N-N) Make it zero to whole the equation or Not Please clarify me ? sir after 9 months you not replied my msg please clarify this
the term N will not be considered
Time complexity should be O(n!) Here?
Yes, i have same doubt
Yes it should be O(n!)
Sir can we conclude as O(n!)?
I have been searching this topic from a while and believe me no one on youtube could explain it as good as you did thankyou and keep making more videos
Sir iska Time Complexity n! kyu nhi ho sakta?
Thanks for you videos Sir
same doubt
Same doubt here. Mujhe lagta hain yeah O(n!) Hi hoga
n*(n-1)*(n-2)*(n-3).......1 =n! Only why you write O(n^n)
Sir, shouldn't we take n steps to get n-(n-1) cause for 0th step we got n-1, for st step we got n-2 and so on
Thanqq sir... Aapse Acha or koi nhi pda skta...aap free me itne ache lecture provide krwa rhe ho hme.. thanqq soo much
This is so wrong. This problem is for solving factorial using recursion. The time complexity of this is O(n)
Hi i need some hrlp do u help please??
@@huriarauf189Hi, I wish I could help. I had commented when I was in college. Now I have forgotten everything
@@jotarokujo5043 ohk am facing algorithm problems
@@huriarauf189 same problems with me
Certainly! Let's solve the recurrence relation T(n) = n * T(n-1) with the base case T(1) = 1 using the substitution method.
1. Base case (n = 1):
T(1) = 1
2. Assume the formula holds for T(k):
T(k) = k * T(k-1)
3. Substitute this assumption into the original recurrence relation for T(n):
T(n) = n * T(n-1)
T(n) = n * (n-1) * T(n-2)
T(n) = n * (n-1) * (n-2) * T(n-3)
...
T(n) = n * (n-1) * (n-2) * ... * 2 * 1 * T(1)
4. Now, replace T(k) in the assumed formula with its expanded form:
T(n) = n * (n-1) * (n-2) * ... * 2 * 1 * k * T(k-1)
5. Simplify the expression:
T(n) = n!
So, the solution to the given recurrence relation is T(n) = n! (n factorial).
it's good to watch these videos before exam rather than attending those boring college lectures.
If Loud and Clear had a face❤️❤️.
I was trying to understand what was written in book and watched this video. Guess what now i open boom just to know next topic🙏🙏.
No one can teach more clearly than you sir.
He's worst
Check other great explain
@@imfromparalleluniverse4504then suggest other channels
@@imfromparalleluniverse4504 then why r u here bro...
@@imfromparalleluniverse4504 1st leave parallel universe
Sir but I have a doubt why it is not O (N!) because for large N 2/N and other terms like that ytend to be zero and N^N will be tend to infinite resulting in an indefinite form
Kamaal he👍🏻
Thank you bhai. This topic was confusing during the semester when I was studying DAA. But after practicing recursion questions in DSA and watching this video, it finally made sense for me.
I am an MCA student and your videos helps me to understand the topic thoroughly, Keep growing!
😇
Bhai am also doing mca 2nd semester
mam is it worth to go for mca or look for any job.... i am a bsc cs student
@@priyansh6978 It depends on you. If you want to pursue a master's go for it. If a job is your priority go for a job.
much appreciated teaching method THANKYOU ....
A tip: you can watch movies on Flixzone. Me and my gf have been using it for watching all kinds of movies lately.
@Kylen Cannon yea, I've been using Flixzone} for since december myself :D
@Kylen Cannon Yea, been watching on flixzone} for since december myself :)
but sir .......n*(n-1)*(n-2)*(n-3)...........3.2.1 = n! bhi likh sahkte hai na sir....to itna complex kyo kiye sir ....N KO COMMON LEKAR????
Watching during exam😅❤
If series is n*(n-1)*(n-2)*.....*1 then isn't it n! ?
Same question. Why not n!
n^n is called factorial time complexity only because n^n > n! so it will cover all the cases of n! and inturn using n^n makes the maths easy.
@@himanshumaheshwari3210 yes, true
Wrong answer! Time complexity should be O(n)
No it should be O(n!)
I have one small question; why cant we write O(n!) instead of O(n^n)
bro did you get the answer? If you have answer of your question then please share
Thanks!
If it is like T(n) =T(n-1)*n^n please
Solve this qn also sir
Sir it is backward substitution or forward substitution
Superb teaching sir 👌
the series is equal to n!.
not n^n
Correct answer is O (n)
Plz solve by
substitution method T(n) = T(n - 1) + T(n/2) + n
Sir you are just like Physics Wallah Sir. Thank you for your valuable classes.
Sir shouldnt the complexity be o(n!)??
can you please help me solving this recurrence relation T(n)= n*T(n-1) + n^2 ?
Very helpful all your videos but sir y niche black m wording likhke ati h to hm ache s method dekh ni pate iski vje s vo hide hojate h🙄
This isn't substitution method, this is iteration method for solving recurrence relation.
4:45 bhai x(n-(n-1)) ? kaise kr lete hu ?
ye tu x(n- n ) hona chaheye...aur agar n-1 hai tu pir tu x(n-1 - (n -1) ) hona chaheye
For worst case it is O(n^n) and for best case is it omega(n!)?
@@sohamnandi4708 I am asking not answering.
Same doubt I have ...
well explained
that is iteration method not substitution method
Thank u sir for this wonderful video
...
Please make videos on solving problems by recurrence tree method ..
Sir you didn't make a lecture on some topic I don't understand anyone I am having a hard time.
Can't we write it as O(n!) as it's 1 * 2 * ... * n - 1 * n???
Thnk u sooo much
Many many thanks from Türkiye :)
I didnt get why is it not factorial time?
Bro he is one of the best teacher. He only likes the comments which are compliment for him. He never clears doubt.
@@Abhay.Bhandari was this a compliment for him?
@@ramakrishnasen4386 it depend on sir. How he will take this. By the way from my side its a good compliment.
The time complexity of factorial algorithm is O(n) because we conside n*T(n-1) as T(n)=T(n-1)+1 please rectify it .Here +1 if for multiplication it is not n-times
I think your second last step is wrong, where you take common of n. If you multiply n(1-1/n) it will come out as (n-1/n) = (n^2 -1)/n
And you can't eliminate n^2 by n while there is minus
Idk if i am wrong
yaha and ni(n factorial) kyu nahi ho sakta hai ??
u r simply superb... i too taught Daa ... but watching ur videos make my day
Best teacher ever!!!
sir i think it should be O(n!), we can not interchange O(n ^n) and O(n!) time complexities
Sir !! Your Level of Teaching is very closer to our thought.. I really like your way of Teaching ...
Why didn't we write O(n!) ?
*******Order of N****** O(n) is the correct answer.you calculated wrong time complexity.
sir, n*n-1*.....3*2*1 isko sidha n factorial nhi likh skte? ya fir O k andr factorial sign nhi ata?
Please explain about iteration method also🙂
some one tell me last ma 3*2*1 kasy aya????
If we take n = 100 for the series n*(n-1)*(n-2)......T(1) then the series will be like 100*(100-1)*(100-2)....(100-97)*(100-98)*T(1), the last term will be 1 as T(1) = 1
@@kirisakiElla Please explain again ke end mai 3 2 1 kese agya
@@hannanbaig7888 Last term given hai T(1) and according to question T(1) =1 and our series is n*(n-1)*(n-2)*(n-3)......T(1), so it means at every step the value of n is decreasing by 1 until it reaches the last term T(1) = 1, So for example if we take n=100 (put 100 in place of n in the series) our series will become 100*(100-1)*(100-2)*(100-3)....(100-97)*(100-98)*T(1) which is 100*99*98*97....3*2*1
Can't we write it as O(n!)?
why did you take n common in the last step when it could be seen that it is a factorial representation? that means n!.
Sir why we are elementing T(n-3) reason ??
Thank you sir for make this video and this is very helpful.
Well its Iteration Method
Sir how can we solve 2T(n/2)+2 power k
dude, which language is this ?!
That's Hindi.
@@bykenvisions is that Hindi or kinda hybrid of English and Hindi, because some of the sentences sounds like English
@@yigithansaglam9128 Bruv he is not completely speaking in hindi, he is using english words in between. You can call that a hybrid if you wish so. If you watch carefully u will be able to understand it. Maths has no language mate.
Kuchh bhi samajh nanhi araha hai
Mein aur bhi confuse ho jaa raha hun
Thank you sir 🙏🏻 This is very clear explanation.
It's hard to understand when he's going back and forth from languages
completed
Can someone say that this recurrence expression is for which problem (matrix multiplication, knapsack , maximum sub-array, etc)?
As we see here we have n * (n-1) * (n-2) * ..... * 2 * 1. Even if we multiply the terms, the product here would be a polynomial of order n. That is the largest term of the product is n^n. Can we say that T(n) is O(n^n) by citing this reason? Idk if my understanding here is right here, correct me if I am wrong.
As i feel its a no.but not 100% sure. If we didn't take n out of the bracket, we get O(n) = n! right? which is much lower than n^n?
if base condition is not available
what is the name of the algorithm with this recurrence relation? someone help, please
why n power n can't we say n factorial time complextiy
Leaning currently this Playlist of DAA .Thank you so much sir ❤.Keep growing and keep smiling 😊
kuch samaj meh aya kya
We start with the recurrence relation:
𝑇(𝑛)=𝑛×𝑇(𝑛−1)
T(n)=n×T(n−1)
Now let's repeatedly substitute to expand the terms:
Substitute 𝑇(𝑛−1)
T(n−1):
𝑇(𝑛)=𝑛×𝑇(𝑛−1)=𝑛×(𝑛−1)×𝑇(𝑛−2)
T(n)=n×T(n−1)=n×(n−1)×T(n−2)
Substitute 𝑇(𝑛−2)
T(n−2):
𝑇(𝑛)=𝑛×(𝑛−1)×(𝑛−2)×𝑇(𝑛−3)
T(n)=n×(n−1)×(n−2)×T(n−3)
Substitute 𝑇(𝑛−3)
T(n−3):
𝑇(𝑛)=𝑛×(𝑛−1)×(𝑛−2)×(𝑛−3)×𝑇(𝑛−4)
T(n)=n×(n−1)×(n−2)×(n−3)×T(n−4)
General Form:
Continuing this process, we observe a pattern. After
𝑘
k steps, we have:
𝑇(𝑛)=𝑛×(𝑛−1)×(𝑛−2)× ⋯ ×(𝑛−𝑘+1)×𝑇(𝑛−𝑘)
T(n)=n×(n−1)×(n−2)×⋯×(n−k+1)×T(n−k)
This expansion continues until we reach the base case, which is typically
𝑇(1)=1
T(1)=1 (it's given in the recurrence).
Final Step (Base Case):
For
𝑘=𝑛−1
k=n−1, we reach:
𝑇(𝑛)=𝑛×𝑛−1)×(𝑛−2)×⋯×2×𝑇(1)
T(n)=n×(n−1)×(n−2)×⋯×2×T(1)
Given that
𝑇(1)=1 we get:
𝑇(𝑛)=𝑛×(𝑛−1)×(𝑛−2)×⋯×2×1=𝑛!
T(n)=n×(n−1)×(n−2)×⋯×2×1=n!
Conclusion:
So, by using the substitution method, we've confirmed that:
𝑇(𝑛)=𝑛!
The recurrence relation represents factorial growth. Thus, the time complexity is
𝑂(𝑛!)
Correct me if i am wrong but in my opinion, this is how this question should be solved. A discussion would be appreciated.
shouldn't it be n! ?
Wrong explanation! Be Aware
Sir this is called iteration method not substitution...
Shouldn't the answer be O(n!).
time complexity of factorial is O(n) or O(n^n) ?
O(n)
its O(n^n). See in worst case we take upper bound that is highest possible value. For n! if we expand it it will give us n number of values n times (i.e n(n-1)(n-2)....). We also know that while finding O(c) we take it as O(1). So, to summarize O(n!) => O(n*(n-1) * (n-2)....1) => O(n*n*n...n) => O(n^n)
thnx alot sir🙏🙏❤❤
N factorial it should be and not pow(n,n)