L-2.3: Recurrence Relation [ T(n)= n*T(n-1) ] | Substitution Method | Algorithm

Подписаться 1,9 млн

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

50% 1

#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 RU-vid: / 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/gatesmashersofficial
► Follow us on Threads: www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:
Email us at: gatesmashers2018@gmail.com

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

18 янв 2020

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

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

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

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

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

Teachers in College🤡 Teachers in RU-vid(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...❤

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

Thanqq sir... Aapse Acha or koi nhi pda skta...aap free me itne ache lecture provide krwa rhe ho hme.. thanqq soo much

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

Thanks a lot sir... Love your tutorials. May god bless you :) Thanks for being so good :)

@harini.a7934 4 года назад

Thank u sir for this wonderful video ...

@ShivamThakur-rt6js 2 года назад

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)

@jigz3903 Год назад

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?

@sabihafirdous1345 Год назад

@@jigz3903 same qsn..

@damianlarocque4958 Год назад

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!)

@bitoffbalance4021 Год назад

@@damianlarocque4958 you sure ?

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

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 �!

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

Thank you sir 🙏🏻 This is very clear explanation.

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

You make this subject easy for me... Thanks

@younus.athlete Год назад

Sir !! Your Level of Teaching is very closer to our thought.. I really like your way of Teaching ...

@pkclashing3805 11 месяцев назад

As usual crystal clear explanation ❤

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

u r simply superb... i too taught Daa ... but watching ur videos make my day

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

this is the iterative method to solve the recurrence relation

@amanullahsiddique3451 Год назад

Thanks a lot sir for clearing this concept...

@AmitKumar-ix3kq 3 года назад

Sir aap kitne pyaar se padhate ho. Thank You

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

No one can teach more clearly than you sir.

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

He's worst

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

Check other great explain

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

@@imfromparalleluniverse4504then suggest other channels

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

@@imfromparalleluniverse4504 then why r u here bro...

@theabhish1 Год назад

@@imfromparalleluniverse4504 1st leave parallel universe

@157_anweshasahoo7 2 года назад

Thank you sir for make this video and this is very helpful.

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

Best teacher ever!!!

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

it's good to watch these videos before exam rather than attending those boring college lectures.

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

Gurujee shandar jabardast zindabad

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

Many many thanks from Türkiye :)

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

much appreciated teaching method THANKYOU ....

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

A tip: you can watch movies on Flixzone. Me and my gf have been using it for watching all kinds of movies lately.

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

@Kylen Cannon yea, I've been using Flixzone} for since december myself :D

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

@Kylen Cannon Yea, been watching on flixzone} for since december myself :)

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

I am an MCA student and your videos helps me to understand the topic thoroughly, Keep growing! 😇

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

Bhai am also doing mca 2nd semester

@priyansh6978 Год назад

mam is it worth to go for mca or look for any job.... i am a bsc cs student

@aayushigadekar2254 Год назад

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

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

Sir, Can we write it as O(n!) ?

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

yes

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

Finally i found perfect lecture for that topic. Thanku sir🎉

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

Super simple ...thanks a lot🙏

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

Kamaal he👍🏻

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

Thanks, Brother, this video saved me today.

@Ajinkya_Chirde_07 Год назад

great explanation sir❤

@KING-ni4ze 2 года назад

Sir you are just like Physics Wallah Sir. Thank you for your valuable classes.

@joshwzr1257 Год назад

I was confused till I landed on your video. Thnx

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

Superb teaching sir 👌

@Phoenix-wr6rn 2 года назад

Please explain about iteration method also🙂

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

Leaning currently this Playlist of DAA .Thank you so much sir ❤.Keep growing and keep smiling 😊

@anujpawar3812 3 месяца назад

kuch samaj meh aya kya

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

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?

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

Try to expand n! and you'll find n number of n's, and just multiply them

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

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)

@damianlarocque4958 Год назад

@@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!)

@satyasnigdhapani8409 Год назад

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

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

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.

@chiragt.lakhani1300 3 года назад

Thanks 😊

@coder_boy Год назад

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???

@mhmitsme Год назад

His teaching way is too better than anyone as well as he's handsome too👀💖

@DineshSingh-hx5kw 2 года назад

Owsm video

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

Your videos are really very helpful and easily understandable sir👏👏😁

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

Video is Useful 👍

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

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

@saifaliit4579 Год назад

Great sir

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

well explained

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

Thx alot I salute you

@sumannath__45 12 дней назад

You are great teacher ❤😊

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

Appriciated❤

@RajeevKumar-pf2wt 3 года назад

Thanku so much sir

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

perfect explanation

@GAU-C--RATNAKANTAHANSE 3 года назад

Thank you sir....

@068_gauravchakraborty 2 года назад

thanks a lot sir

@vigneshviswanathan3296 Год назад

Sir can we conclude as O(n!)?

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

Please make videos on solving problems by recurrence tree method ..

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

Thanks sir,love from Bangladesh

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

sir aap bohat acha parhate hain please pakistan me ajayn karachi wali fast university me akr sary subjects parha den

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

Hahaha

@mr.mohammedmobinakhtar2617 3 года назад

Plz solve by substitution method T(n) = T(n - 1) + T(n/2) + n

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

Very nicely taught...thankyou😄

@Mandeepsingh-jo5cf 2 года назад

Thanks!

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

Thank you sir 👏👏👏💖💖💖💖👌👌👌👌👌☺

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

thnx alot sir🙏🙏❤❤

@vaibhavbiyawala9165 Год назад

Can someone say that this recurrence expression is for which problem (matrix multiplication, knapsack , maximum sub-array, etc)?

@sameerakhatoon9508 Год назад

can you please help me solving this recurrence relation T(n)= n*T(n-1) + n^2 ?

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

Sir is topic pe please kuch questions solve karwa dijiyega.. previous year wale

@pavanavasarala2873 9 месяцев назад

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

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

🙏🤗

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

Please make a video on recursion tree method

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

thnku so much sir

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

Thnk u sooo much

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

sir, can u provide some practice ques?

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

Thanks bro

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

Sir, can't we say time complexity of N factorial?! In this case!?

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

Yes, we can but the answer will remain same only [O(n*n)].

@thedemonlord300 Год назад

@@koushikkanumuri253 how

@koushikkanumuri253 Год назад

@@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)]

@damianlarocque4958 Год назад

@@koushikkanumuri253 What are you trying to say? The time complexity of an algorithm which runs in n! ...is well, O(n!)

@Wtk_Ncs Год назад

@@koushikkanumuri253 for n! It will be O(n power n) order

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

thanks sir

@2f4u89 3 года назад

Sir, what if End condition is not given then?

@subantikujur3244 Год назад

Tq so much sir😊😊

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

Love from Bangladesh.

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

This is forward or backword method???

@samanmustafa-zy7yu 2 месяца назад

You are best 💖 sir

@eekshitasai2663 11 месяцев назад

Sir it is backward substitution or forward substitution

@rajat9302 Год назад

Sir isski time complaxity O(n!) bhi toh ho skti hai n??

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

what is the name of the algorithm with this recurrence relation? someone help, please

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

sir, n*n-1*.....3*2*1 isko sidha n factorial nhi likh skte? ya fir O k andr factorial sign nhi ata?

@pawanpt2682 9 месяцев назад

Sir how can we solve 2T(n/2)+2 power k

@shantanukapse3740 Год назад

Sir shouldnt the complexity be o(n!)??

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

Sir why we are elementing T(n-3) reason ??

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

le fir aa gaya , jab to todenge nahi, tab taj chhodenge nahi

@learncseasily3385 Год назад

Isme k times kyu nahi lia is problem mai ??? Can anyone explain ?

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

❤️❤️

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

Recursion Tree videos neeeded

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

Time complexity should be O(n!) Here?

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

Yes, i have same doubt

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

Yes it should be O(n!)

@154poojadas7 3 года назад

If this is substitution method then what is iterative method

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

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

@slov1ker583 Год назад

sir i think it should be O(n!), we can not interchange O(n ^n) and O(n!) time complexities

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

Sir, How to solve the given recurrence relation? T(n)= 2^n T(n/2) + n^2

@aizy_crazy_dubbing Год назад

T(n) = 2^n T(n/2) + n^2 We can use the master theorem to solve this recurrence relation. Let's first take the logarithm of both sides of the recurrence relation: log T(n) = log (2^n T(n/2) + n^2) Using the logarithmic property, we can simplify this expression as: log T(n) = n log 2 + log T(n/2) + 2 log n Now, let's define a new function S(k) such that S(k) = log T(2^k). Substituting this in the above equation, we get: S(k) = 2^k log 2 + S(k-1) + 2k Simplifying this expression, we get: S(k) = k 2^k + (log 2) (2^k - 1) Using the definition of S(k), we can write T(n) as: T(n) = 2^S(log n) Substituting the value of S(k) in this expression, we get: T(n) = n (log n + 1) Therefore, the solution to the given recurrence relation is: T(n) = O(n log n)

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

If it is like T(n) =T(n-1)*n^n please Solve this qn also sir

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

time complexity of factorial is O(n) or O(n^n) ?

@DEVANSHGOEL-dq1wh 3 года назад

O(n)

@ShivamThakur-rt6js 2 года назад

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)

@iamghost142 3 месяца назад

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