L-2.4: Recurrence Relation [ T(n)= 2T(n/2) +n] | Substitution Method | Algorithm
ฝัง
- เผยแพร่เมื่อ 31 ส.ค. 2021
- 👉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/gatesmashersofficial
► Follow us on Threads: www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:
Email us at: gatesmashers2018@gmail.com
![L-2.5: Recurrence Relation [ T(n)= T(n-1) +logn] | Substitution Method | Algorithm](http://i.ytimg.com/vi/JCX8noGdY7k/mqdefault.jpg)
![L-2.5: Recurrence Relation [ T(n)= T(n-1) +logn] | 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)
![[TH] VCT Pacific Stage 2 - Week 4 Day 1 // PRX vs RRQ | GE vs GEN](http://i.ytimg.com/vi/iIi2_04jGr0/mqdefault.jpg)
This channel needs more recognition and reach! Amazing work!
Hi
honestly my savior , you're the best fam , you always keep things simple. love your videos keep doing 'em
Awesome explanation! You just gained another subscriber!
Dear teacher,
I wish you a happy teacher's day. Thank you for being the guide and for inspiring me to do well in my studies. You are the best teacher
HApPy tEaCheR'$ dAy
Owsm sir...keep doing this we extremely need this❣
god bless you sir...most useful one!!!
love you sir, The way of your explanation is too good
Sir bhot Bdhya samjhaya aapne
Glad that I found this channel before time.
Nah man U deserve love. really grateful my frnd u just made it simple
You are amazing!! Btw it will be great if you could include step count method, tabular method for calculating time complexity of an algorithm and also PRAM algorithms, string matching algorithms too
Sir your explanation and you both are outstanding
Great Explanation 😊😊
Keep it up ❤️💙
Sir you are an absolute legend
Sir congratulations to complete 6lakh subscriber
So what is the difference between iterative and substitution method in this qtn sir?
First for 2^2T( 2(n/2^3) ×n/4) +2n
we need to multiply 4 × above whole bracket equation then we have the value of 2^3T((n/2^3)× 4n/4) +2n
After divided 4n/4 we got n then add n +2n = 3n
After that we have the equation
2^3T(n/2^3)+3n
Code with Ayush
Thank you so much sir 💗☺️
you're taking it in complicated way my college teacher explains it in very simple and easy way
Sir good work 👏.
Achi Tara samajh ahi ha..
Bhai Allah aapku himmat de 6 lakh sus.but 8 hours views only 800 ❤️❤️❤️
Very well explained. Mujhe yeh video lagatar 3 baar dekhne pada par mera concept clear ho gaaya. Thank you very much sir!
Best Teacher ever.
Insane so good❤
Happy Teacher's day sir
🙏✨💫
Every one make sure u like every one of sir's vdo other wise u will forget this in ur exam
Srji apney college ke prof se zyada toh idhar acha samajh aa rha hai ... koi bhi stepwise explain nahi karta itna clearly kahi bhi
Beta Dil se padhate he iss liye padho padho
Thanks sir,
Aaj me phone leke gaya tha Exam hall me aur ye question aagaya 😂
Course: B.E (IT Branch)
Awesome explanation
Congo sir 600k
Love from pak ❤️
Thanks sir 😊
HAPPY TEACHERS DAY SIR!
The way sir says subscribe bahut zaroori hai
Hits hard more than time complexity 2 ki power n
sir u made a mistake on 3:39 when 2^2 is cancel by 2 how it is still 2^2 i mean the ans should be 2 just........................
bro multiply 2 with bracket... you will get 4T(T/4)+2n/2 and in next step take 4 as 2^2... got it..!!!
Thanks bhai@@xenonudaykhandare2836
Missing the old board😌
thankyou so much sir
Tq so much sir
sir pls explain recurrence relation by iteration of second order equation
Hello Sir, Answer is T(n)=n+nlogn then how it become O(nlogn). It should be Ω(nlogn), isnt'it?
Acha smjate ho🔥
you are very very very good teacher 😊and looking like 😍😎❤
Hi VARUN SIR !
HOPE YOU ARE DOING GREAT 😃
I have one confusion if
= 2 ( 2T (n/4) + n/2 ) + n [ IN THIS STEP HOW YOU HAVE CUTTED THE VALUE 2 OF n/2 and the outer 2 ( i.e. outside the bracket )
= 2^2T ( n/2^2 + n/2 + n)
= 2^2T ( n/2^2 + 2n )
HOW IS THIS POSSIBLE BEACAUSE YOU ALREADY CUTTED THE VALUE 2 FROM THE FIRST LINE I HAVE MENTIONED... PLEASE CLEAR OUT THIS DOUBT
He did Right check you again , he just multiply 2*n/2 and here 2 is cancle out
same ques
the first 2 is multiplied individually inside the bracket. [ 2(2T(n/4)) ] + [ 2*n/2 ]
Bhai mereko bhi ye doubt hua tha. Dobara uss line ka calculation karo individually. Hojaeyga.
I also had this doubt
Great sr
Thanku sir❣️
thank you sir
👍
sir just a doubt , why do we always take log both side always , i never understood this , 7:29 plz reply fast ...
Sir, English version of your Lectures. Very great content ❤❤❤❤❤❤❤❤❤❤❤❤❤❤
Sir please upload AI and ML playlist
Please 🙏🙏🙏
Love the explanation ❤ No doubt you are a great teacher 🙏🏼
But, Lord knows who edits these videos! Reminding every other minute "subscribing" the channel is so annoying.
Best
LORD SPOTTED 🛐🗿
Sir how we cancel outer 2 with inner n/2 in 1st two equ's substitution. Coz outer 2 multiplied by all values.
Same question sir
2 is cancelled in multiplication with n/2 not in overall bracket after being multiplied by 2T(n/4).
Same question plz sir
you first do 2 x 2T(n/4) making it 2^2 T(n/4) then we do 2 x (n/2) which cancels 2.
@@parthbatta7968 thanks!
Sir muzhe mathematical induction and recursion ka lec chaiye tha ..video send kro na ap
hats of ustad g 🫡💯
Finally digital board😌
2-way Merge Sort ka recursive equation
How can i solve T(n)=T(n/4)+T(n/2)+n² using recursion tree method
This relation is of which sort technique?
that was the time complexity for merge sort
completed
How can u divide 2 and n/2
Sir n log(n)
Dominating kaise hoga....
For ex:
9 > 9log(9)
Sir please do videos in english also 🙏
🙏🙏🙏🙏🙏👍👍👍👍👍
if you made these videos in english, it will be a great help to south indians who doesnt understand hindi.
Can we call this as iteration method??
I think there is some mistake in the solution..if you are cancelling outer 2 with n/2 then how again you got that 2^2 ?
there is a mistake in the step where you cut 2*2 by 4
can anyone plese tell where these n^2 and n^3 are coming from plz
sir i am facing difficulty in substitution method and iterative method because the method that u use is same as our teacher taught in iterative method . so what is main difference between them can you help me
Sir guide and help my DAA Paper is on monday 14 april
Sir computer vacancy ke preparation hoge kya
I wish there is english subtitles for this sir :(
There are...
3:13
if i do this same question using Master method then the answer is O(n) . why ?
Because u done mistake
Sir can you please make a video on following equation. 8T(n/2)+n^2 here T(1)=1. Plz sir after 15 days I have exams and this question is important 🙏
Bhai n/2 karke solve karta chala ja aa jayega
15 din me ek question toh khud se solve kar le bhai ab toh 1 sal ho gye hue kya??
Sir please solve this question by reccurance relations by substitution method an= an-1 +n× 3 power n where a not =1
2 ( 2T (n/4) + n/2 ) + n [ IN THIS STEP YOU MULTIPLY 2( 2T (n/4) + n/2 ) SO [2^2T(n/4)+2^(n/2)] + n [NOW IN THIS STEP CUTTED THE VALUE OF 2 IN THE FOLLOW EQ 2^(n/2) AND THE FINAL RESULTS OF THE GIVEN STEP IS 2^2T(n/2^2) +n+n => 2^2T(n/2^2) + 2n
2 ki multiple kar di andar n se toh 2n upon 2 hogya fir 2 cancel hogya bacha n +n
Sir agar n ke badle cn raha ga to kuch change ho ga kya
thanks
yra equation kay numbers peh circle to karo sara time us peh stuck rha
Where did T go in 4th step
there's a mistake, where's the extra 2 coming from
By solving this question you did back substitution method wrong check it once.
bhai shuru ki beat ka link bhej de, rap karna hai uspe
yeh 2 square or 2 cube khn se aarha hy?
ye n/2k kaise =1 daal skte ho marzi se
And where didn T go
1:00 aur device is suscribe kara doo...Chad moment 😎😂
Sir 2 square kahna se aya uspe
sir 2 ko bracket open kr ke 2t se multiply kr raha ha fir n\2 se usko cancel kasa kr raha ho
By bodmas first solve bracket you have to first multiple 2T by 2 so that it became 2 [4T (n/4) + n] /2 this how it is cut outer 2 by deninometer 2
2 [ 2T (n/4) + n/2] + n
2 [ 4T (n/4) +n ] / 2 + n
2 square kaise aaya?
u changed the board
Sir??
Is this Iteration Method?
Yr batao yeh iteration ha I am also confuse
Like here if you don't understand hindi but this be your only option🤣
sir 2 sqaure kaise hua isme
2 already tha ak or 2 aya isliye
Ye toh galat hai
Sir u forget to cut one of the 2's
didnt understand on 3:28 how 2^2 is made plz can anyone explain me this !!!!!!!!!!!!!!
By bodmas first solve bracket you have to first multiple 2T by 2 so that it became 2 [4T (n/4) + n] /2 this how it is cut outer 2 by deninometer 2
2 [ 2T (n/4) + n/2] + n
2 [ 4T (n/4) +n ] / 2 + n
@@rutikpatil6758 thanks
don't give an english topic if you will not speak English!
If you're not Indian.. Tell your people from your country who speak the same language to make tutorial video