1 votes 1 votes Find time complexity? a) T(n) = T(n/2) + pow(2,n) b) T(n) = T(pow(n,1/2)) + n c) T(n) = 16T(n/4) + n! d) T(n) = pow(2,1/2)*T(n/2) + log n can we apply master theorem on the above problem? Daniyal89 asked Sep 16, 2018 edited Sep 16, 2018 by Daniyal89 Daniyal89 3.1k views answer comment Share Follow See all 19 Comments See all 19 19 Comments reply sakharam commented Sep 16, 2018 reply Follow Share Yes, you can apply master's theorem in each of the cases, In b) you will need to change the recurrence relation a bit to solve it. 0 votes 0 votes Daniyal89 commented Sep 17, 2018 reply Follow Share Can you explain? 0 votes 0 votes sakharam commented Sep 17, 2018 reply Follow Share https://gateoverflow.in/239897/geeksforgeeks This is a similar problem to b) In case if u find it difficult to understand let me know. Note: Also I assume that the base case is T(n)= thetha(1) (since you have asked to solve it with masters theorem and we can apply master's theorem only when the base case is constant) Source: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Generic_form or lemma 4.2 from Intro to Algo by CLRS 0 votes 0 votes Mayankprakash commented Sep 17, 2018 reply Follow Share @sakharam Can you please solution of option d 0 votes 0 votes sakharam commented Sep 17, 2018 reply Follow Share @Mayankprakash Answer:$\Theta (\sqrt{n})$ Assuming base case is thetha(1) Applying Master's Theorem, a=21/2 , b=2, f(n)=logn Case 1 applies: logn=O(nlog2$\sqrt[]{2}$ - ε) logn = O(n1/2 -ε) ,ε>0 Hence T(n)=$\Theta (\sqrt{n})$ 1 votes 1 votes Mayankprakash commented Sep 17, 2018 reply Follow Share Thanks 0 votes 0 votes Daniyal89 commented Sep 17, 2018 reply Follow Share @sakharam Is not in O(n1/2-e) has to polynomially larger than log n to apply master therom 0 votes 0 votes sakharam commented Sep 17, 2018 reply Follow Share @Daniyal89 I didn't understand what you are saying Are you asking whether n1/2- ε is polynomially larger than logn? 0 votes 0 votes Daniyal89 commented Sep 18, 2018 reply Follow Share @sakharam Due to this I am confused.....like in Question (a) How to 2n is polyphonically larger than n 0 I know that 2n is asymptotically greater than n0 0 votes 0 votes Verma Ashish commented Sep 18, 2018 reply Follow Share How can you apply master's theorem on a and b ? 0 votes 0 votes sakharam commented Sep 18, 2018 reply Follow Share I will explain you what that meant. Usually we see, nlgn/f(n) is greater than nlogba ,and then we proceed with case 3, and then we check the condition that for sufficiently large n... the same thing in the first recurrence in the image. Why in the 2nd recurrence in the image f(n) is not polynomially larger than nlogba? f(n)=nlgn Is nlogn = $\Omega$(n1+ε) ?where ε>0 {Here we check whether its polynomially larger} For the above condition to satisfy nlogn >=n1+ε should satisfy Lets divide by n on both the sides Is logn >= nε ? ε>0 Think of the smallest value of ε, lets think of one Lets say ε = 1/109 Now if u see1 log n will be lesser than n1/1000000000 Its easier to see why log n is lesser for very large value of n log both and wer get loglogn and 1/109*logn So no matter what ever value of epsilon >0 we put we can't proceed with the third case. :-) 2 votes 2 votes sakharam commented Sep 18, 2018 reply Follow Share And to your previous question: Is n1/2-ε polynomially larger than log n? Lets see Lets say ε=1/4 which means 0.25 which satisfies ε>0 so n1/2-ε becomes n1/2 -1/4= n1/4 Is n1/4 > log n Yes, for large values of n Its easy to check, take log on both the sides and we get 1/4 logn and log log n So yes in case 1 the condition satisfies :-) 1 votes 1 votes Verma Ashish commented Sep 18, 2018 reply Follow Share Can you see and reply the last comments of this https://gateoverflow.in/227814/introduction-to-algorithms Please.. 0 votes 0 votes Daniyal89 commented Sep 18, 2018 reply Follow Share @sakharam Can you explian option (a) like you did these examples 0 votes 0 votes sakharam commented Sep 18, 2018 reply Follow Share Sure, a=1, b=2 f(n)=2n Does case 3 apply? 2n >=nlogba+ε ? ε>0 2n >=nlog21+ε ? 2n >=nε ? [This needs to be true for proceeding with 3rd case] Lets try to make this false Lets take ε =1099 But no matter how large ε is 2n will be greater for very large value of n Lets see why Lets take log with both nlog2 and 1099 log n So 2n is larger So now we can proceed to the second part of case 3 Please read second part of case 3 from Cormen, Is af(n/b) <=cf(n) for some constant c<1 and all sufficiently large n? If yes then case 3 is satisfied. We know a=1, b=2 and f(n)= 2n we need to check f(n/2) <=c*f(n) for some constant c<1 and all sufficiently large n i.e. 2n/2 <= c* 2n or not? i.e. 2n/2 <= c*2n? Lets say c=1/2 = 2-1 =0.5 which is less than 1 2n/2 <=2-1* 2n 2n/2 <=2n-1 for n>=2 Hence case 3 satisfied and T(n)= $\Theta$(2n) 2 votes 2 votes Daniyal89 commented Sep 18, 2018 reply Follow Share Thanku @ sakharam 0 votes 0 votes Priyadrasta Raut commented Nov 2, 2019 reply Follow Share What is the answer for option b using master's theorem??Is it O(n)? 0 votes 0 votes sakharam commented Nov 5, 2019 reply Follow Share @Priyadrasta Raut Yes its $\Theta (n)$ 0 votes 0 votes amcodes18 commented Jan 30, 2020 reply Follow Share i still cant solve 2nd one using masters theorem , can anyone help? 0 votes 0 votes Please log in or register to add a comment.