L-2.7: Recurrence Relation [ T(n)= T(n/2) +c] | Master Theorem | Example-2 | Algorithm

#MasterMethod#algorithm

►Design and Analysis of algorithms (DAA) (Complete Playlist):

Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
► Operating System :
►Database Management System:
► Theory of Computation
►Artificial Intelligence:
►Computer Networks (Complete Playlist):
►Computer Architecture (Complete Playlist):
►Structured Query Language (SQL):
►Discrete Mathematics:
►Compiler Design:
►Number System:
►Cloud Computing & BIG Data:
►Software Engineering:
►Data Structure:
►Graph Theory:
►Programming in C:
►Digital Logic:

---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:

[hilal]

Whenever im free, i put on his video on youtube but i dont watch it, so that he gets the views and ads for doing such a great work for free :) @Gate Smashers

[abduljalilmemon]

sir i really appreciate your efforts and your teaching skills. i have a request could you please make videos on iteration and recursion tree method?

[anubhavdas]

I've been following you for almost a year now. It's been really helpful throughout. I've suggested your videos to other students as well. Thank you for wrapping up the whole idea in a few minutes clearly.

[ashashreesarma]

Do we need to necessarily bring down the constant while calculating the U(n) ?
(The one which we multiplied with logn)
Because through the table only the logarithm part is said to be considered

[vaibhavsaran]

T(n)= 8T(n/2) + (n^3/ log^2 n) sir for this question your method does not work h(n) is does not have category for to get u(n)
T(n)=4T(n/2) + (n^2/ log n) same for this question

[jaynarayan]

Sir agar h(n) jo hain 1/log n hain toh kya karenge, U(n) ke liye please explain sir???

[shivangb]

Such an amazing Master theorem explanation! Literally the best on the internet! Thanks a lot for this @Gate Smashers ❤

[teeshasingh]

Where is the Question File?
I couldn't find it in the description box..

Thank you for the amazing lectures sir❤

[nuzhatul]

Sir, practice questions are no longer available there...

[saradindurana]

The running time of an algorithm T(n), where ‗n‘ is the input size, is given by—
T (n) = T(n/2)+ logn, if n > 1 = p, if n = 1
where p, q are constants. The order of this algorithm is—
(a) n2(b) loglogn
(c) logn (d) (logn)2
i am getting loglogn as answer on this problem sir.

[laptopbhh]

sir if log(base2)power(n) = nlog2 = O(n)
then why we put it O(log2N) atlast

[ayushuniyal]

please upload solution of practice questions,

[sutharnisargghanshyambhai]

Is it always the case that we get the log to the base 2 in the third case for U(n)?

[saisravani]

Sir, would U pls attach answers for the qns using substitution method . Using master method it's easy to solve but using substitution method I am not getting ans .
If any one solved using substitution method for the practice qns pls .... provide ans document

[juhimughal]

hello sir, can you please explain this question
The running time of an algorithm T(n), where ‗n‘ is the input size, is given by—
T (n) = T(n-1)+ 1, if n > 1 = p, if n = 1
where p, q are constants. The order of this algorithm is—

[vaibhavsaran]

sir what if we get h(n) = (log n)^-1 then it will go in which case???
the question was T(n)=4T(n/2) + n^2/log n
kindly answer this sir, your method is very effective but I cant get this question
@Gate Smashers

[sujalthakkar]

I can't find the link to the file where more problem questions are given. can you reply me with the link in comment?

[NidhiSingh-qiip]

Sir if there will be log in f(n) then how to solve that by this table for example T(n) =2T(n/2)+n/(log^2n)

[mayanksoni]

Thanks Sir It helped me after 1 year of upload and helpful to others too. 😊😊
Thank You For practice questions 😃!!

[AmberRathour]

Thank you for giving practice questions.
Ab sabke Gate SMASH kar dunga!