L-2.9: Recurrence Relation [T(n)= 2T(n/2) +cn] | Recursive Tree method | 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: [e-mail]

[@learnandtravel7722]

Exam in a hour

[@R00059]

R.I.P

[@Hercules-rf8ry]

2pm bro

[@thewaves2241]

Same

[@meetaaryan5550]

Exam in minutes

[@MuhammadUsman-nn9ff]

To bhai comment kyon karrae o

[@icewiz7347]

Subscribers bahut zaroori hai.

[@defterwings1]

Subscribers bahut zaroori hai.

[@OTAKU_1818]

Last night before exam 😂

[@shambhavirani87]

1 hour before the exam😆

[@programmar-jn4oe]

30 min before exam 😂​@@shambhavirani87

[@zeeshanakhtar8399]

One of the best teachers i've ever found on youtube, may God bless you señor and SUBSCRIBERS BAHUT JROORI HAIN 😁.........Love you 🥰 sir.

[@Nirmala1824]

ap nahi hote toh humara kya hota sir

[@Patra_Kirsani]

DP se ta ledki lag rehi ho... Number share karna ta banta hai bhai..

[@Nirmala1824]

@@Patra_Kirsani chappal ka number chaiye ya jutte ka?

[@Patra_Kirsani]

@@Nirmala1824 Are bhai mojak kar raha thaa... Dil pe kyuin le lete ho yaar

[@pristudyin]

😂😭😂

[@AwsShorriw]

Sir I studied half of my BSCS course from your TH-cam videos

[@AstonMartin-h6k]

Exam in few minutes 😬

[@Forthero_J]

Chuhun

[@ayeshajadoon1045]

Same condition 😰

[@SupaStrikers-pr6bc]

On morning my exam and I am seeing video 😅

[@crazyatul1231]

Bhai konsi degree ka exam de rhe ho

[@cricketclip357]

Solve the following recurrence equations: (8 Marks)
(i) T(n) = 2T(n/2) + 0(n)
(ii) T(n) = T(n - 1) + 0(n)

[@sohangchaudhari1219]

i) O(n log n)
ii ) O(n^2)
Best and Worst case time complexity respectively.

[@जयमहाकाल-स7ड]

agar sir aap ham jaise bachho ko na pda the hote to fail hi jate aapko videos dekh Kar bhut confidence aata hai aur paper bhi achhe se ho jata hai college Vale khud hi confuse rahte hai samjh nahi aata 🙏🙏

[@Manishkumar-yb6xw]

Thank you sir sare sub yahi se pade hai maine hamere teacher kya padte hai kuch pata nahi wo bhi khud confusion mai rehte hai 😂😂
Thank a lot

[@gauravbaviskar1616]

How did you calculate height of tree as " log n " ?? 😔🤔🤔

[@shashankbangera7753]

divide and conquer approach is calculated in log base 2 to the power n where n is the cost(constant).If this doesn't makes any sense then try yourself by using a calculator and putting the equation log base2 (16) answer would be 4. Hope this helps :)

[@ammi4702]

Log is the number of times a number is divided.

[@amankumarsingh3995]

Let at the last leaf of tree
Situation will be like t(n/2^h) in each leaf where h = height
And at the last each leaf should be equal to 1
Then
n/2^h = 1
n = 2^h
Take log both side
Log n = Log 2^h
Log n = h Log 2
H = Log n / Log 2
H = Log n base 2

[@ARSAGAMING69]

Sir humne yaha divide kiu kia hai
n fir 2n fir 3n ....
Esa kiu nahi liya hai ????
Plzz answer 🙏

[@abhishekbandil1737]

Baal katwa liye bhaiya iss vedio mein 😂😂

[@BhagatBhutale..]

Video is useful 👍

[@allinonetechnicalvideosfor7609]

Very nice lecture very helpful 👌

[@allinonetechnicalvideosfor7609]

Thanks for the heart ❤

[@lolind1197]

Sir,mere pass degree to nhi hai koi,but apke channel ki vja se , knowledge bhaut hai,kya mje kisi trah ,job mil skti hai,

[@jashanpreetsingh6056]

hmm

[@amandeep-op2up]

Nice explanation sir 👍👍👍

[@ARSAGAMING69]

Sir humne yaha divide kiu kia hai
n fir 2n fir 3n ....
Esa kiu nahi liya hai ????
Plzz answer 🙏

[@realeconomy5348]

Is there an English version? Please try a(n+1)=3*a(n)^(1/3)/(2+a(n)), a(0)=1/2.

[@AYUSHCHAUHAN-p1m]

love you sir

[@RahulSharma-iu5ox]

thanku sir

[@srithanujbv7387]

subscribers is very important broo !!! Or else u won't understand bro!

[@shubhampatil7449]

Subscribers bhot jaroori hai😂

[@DineshSingh-hx5kw]

Awsm Sir

[@gunjanpandey1466]

I feel one thing from bottom of my heart.... Sir aap sach m bhagwan h kyuki apki whjse hi m aaj 3rd year m hi baki clg m jesa padate h usse to mujhe lgta hai ki m padna hi band krdetii 😂

[@erosbebe3336]

Sir, currently I'm following your DBMS course and that is amazing, also completed your OS playlist. I have a request to make, please make videos on Machine Learning.

[@kripashankartiwari721]

Big fan from vadodara

[@ARSAGAMING69]

Sir humne yaha divide kiu kia hai
n fir 2n fir 3n ....
Esa kiu nahi liya hai ????
Plzz answer 🙏❤

[@neelampaswan861]

Sir m apke bare m jitna likhon utna km h ap bhot achha samjhate ho sir 😊

[@ARSAGAMING69]

Sir humne yaha divide kiu kia hai
n fir 2n fir 3n ....
Esa kiu nahi liya hai ????
Plzz answer 🙏❤❤

[@Drago20041]

sir pls do your content in english sir

[@FireGaming-vq3nh]

Thank you so much sir you save my whole tym☺️🥰❤️

[@nudratfatima7876]

Could you please solve a recurrence problem for me? T(n)=T(n-1) +1/(2^n). It's very urgent. I/m supposed to solve it tonight. I have some more problems like this. I'll really very thankful if you help me solving recurrence problems as I have Final exam tomorrow.

[@MuhammadHuzaifaRauf]

aap ko c nahi likhna chahiye sath..kyun ke c to end pe aye ga :)

[@dasharathkushwaha5753]

Sir polytechnic lecturer ke liye koi course series laiye

[@Aarti-Sweetshots]

I also willing for same

[@Akori_vlogs]

Beta vo polytechnic ko nhi padhayenge chutiye ko nhi padhate h

[@dasharathkushwaha5753]

@@Akori_vlogs I think you are too educated 🙏

[@alokreddy99]

@@Aarti-Sweetshots I will take free class for polytechnic if you interested reply me

[@carrotiq6879]

bhagvan aap k jise beard sab ko de 😍

[@sarfrazahmed4282]

Super

[@DarpaSeven]

thnx Just understood this concept in few mins .keep it up

[@APstudent-y6s]

1:26 ok sir

[@sandipthaware3391]

Congratulations to 10 million TH-cam subscribers

[@venkatkrishna534]

sir very gooodu teaching sir😀

[@tejasvics5766]

Can u teach mee

[@venkatkrishna534]

@@tejasvics5766 per class fee 5k

[@pratibhasahu3015]

Sir meko ye video smjh aa gya lekin isse related questions me doubt h vo kaise clear kru?😢

[@CODINGCHRONICALS792]

so this method is for special case or every case?

[@risualturner5190]

everything is temporary but subscribers boht zaruri hai is permanent

[@soumyajitseth1562]

Sir i have a question that why shuold i take only 3 levels in tree...not more or less

[@turture69]

Aur devices se subscribe karke kya karu jab muje ek hi device se parna hai😂

[@daryasirleo5088]

Who is having exam tomorrow 😄?

[@parultaneja7833]

😩😩

[@motivationalhub3521]

🥺😂

[@shreshthjha997]

Abhi h aadhe ghante bd 😂🤣

[@yaminisahu8110]

Nice explanation sir☺️☺️☺️👌👌

[@bheeshmakarmuri7249]

I am not like you i am studying before two months

[@pritamghosh8916]

Kal subha 6th semester ka exam hain

[@ASIFALI-yj1xh]

marhaba..ya habibi..

[@igf8235]

Yes sir padhai se jyada important h subscribe 💀

[@codexcelai.]

Thank you so much sir❤😍

[@pb56_mems]

Exam in one minute 😊

[@codewithdoge]

Net jrf ke liye padhte padhte ab soch raha ki gate bhi dedu

[@sabrinaafrin3309]

as it is n/2 so we are dividing it in two parts ? Suppose it is n/3 , so we will divide it is 3 parts right ? ..

[@vivekmaru2557]

do let me know if you find the answer for n/3

[@geddamsruthisri5100]

Sir is it possible by substitution method?

[@avishekpatra8613]

Exam in few hours

[@SalimAnsari-cy8iw]

Already in exam hall😅

[@computerguy3550]

thanks bhai🙏🙏

[@emaansiddiqui7674]

you literally save my life and grade before every paper!!

[@saptarshideb]

Kuch nahi hona wala bhai Tera exam mai

[@earnmoneyathome6252]

​@@saptarshideb Bhai nahi behen hai😂😂😂

[@aryanarya72]

sir iska answer subsitution se O(n^2) aa rha hai.

[@TheGlblInvestoor]

nahi bhai nlogn he aaye ga aagar aa ktimes ke equation nikal ke n = 2^k , log n = k log 2 , k = log n aab isse kth equation me put karo answer O(nlogn) ayega

[@micmac2677]

Aur master theorem Se bhi o(n^2) aa rha hai
🤔🤔

[@Mostafijur07_Official]

@@micmac2677 nahi c.nlogn hi ayega
T[n]=n*u[n], h[n]=c, so we can write it as (logn)^0*c then we follow the relation between h[n] and u[n],so u[n]=clogn
so the ans is T[n]=cnlogn.

[@sameergautam5900]

Quiz in a hour 😅

[@sofirequia8615]

Hlo sir plxx make video on decision tree

[@Codeshala12]

Exam in 20 min

[@sipunrout4429]

He looks like Swagger Sharma

[@shaiksartaj8728]

explain about master therom please

[@Ramlakhan123-gg1qk]

Are chaccha algorithm bhi batana tha

[@MayaTech-lm7pm]

Amazing very helpful before one day of exam

[@cricketclip357]

Solve this problem sir please

[@zainulabideen156]

okay

[@mohammadvasiuddin3102]

Thank you sir it helps a lot

[@AsthaVashisht]

Nai smj aya

[@studyafa7159]

6:20 pe kya kar dia smajh nahi aaya

[@nitusah1985]

can you plz solve T(n)= 2t(n/2)+nlogn with substitution method , n>1?

[@daryasirleo5088]

Yes..?

[@parascytheplays2879]

answer is big oh(n); 0(n)

[@abhi34776]

thankyou so much sir

[@_music_club693]

Tq❤

[@a.n.a.n.y.a]

Thank you sir

[@EUCB-ASMITHAAA]

Sir,Can you pls explain in English..Humble request

[@lord_yzal]

completed

[@Howlforgaming]

❤

[@huzaifamalik627]

❤❤

[@souravsalaria7689]

❤

[@TechAndroJavaOfficial]

Thank u🌷

[@nashrodrigues4430]

What about the 2t??

[@subhamsinha8983]

please make a playlist on automata ,agle sem mai autmata hai class mai toh padhai hogi nhi aapse hi padhna hai at the end of sem

[@iakash017]

superb 😃

[@shreyashchoudhary2637]

O(Awesome)!

[@Amanansari003]

#question
can somebody tell me how height is Log-n ?

[@studyafa7159]

vahi to samjh nah aya ....

[@poonawala2303]

formula hai wo

[@suryasikharej5511]

@@poonawala2303 let me explain lets say height is k. so 1st level is 0 and number of inputs is n which we can write as n/2^0 which is n/1 that is n. Then in level 1 n is divided into two parts n/2^1 and n/2^1 now see the power of 2 is same as level. So at kth level it become n/2^k and this n/2^k will become 1 when you reach end . so 1=n/2^k . solving this we get k=log n. where k is the height.

[@HarshithReddyVoladri-hc2lh]

hi

[@virenkalra8918]

Sns

[@muhammadatiq9820]

Sir recurrence relation,iteration method say kesay ho ga .is pr bi koi video bna den....

[@vinayaksharma-ys3ip]

😊😊💯💯👍👍👍

[@Nikcouple]

Thank you sir ...

[@micmac2677]

Sir isko master theorem Se krne pr o(n^2) aa rha hai

[@tusharsahu8587]

O(nlogn) aayega Yaar ध्यान se check करो

[@principalrsr3499]

Thank you sir

[@abhishekh5566]

Thank you sir 😌

[@amirkhan-ok7gx]

2.8 video sy agai mazak kr Raha hai..
Topi pehna raha hai😒

[@sultanhazratali3164]

Great sir

[@sultanhazratali3164]

Thank you sir

[@scalewithsam]

Exam is in next 30 mins 😢😢

[@hope50_78]

I wish I knew Hindi🫠