0 votes 0 votes DS asymptotic-notation + – nilamd asked Jan 31, 2016 nilamd 2.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply nilamd commented Jan 31, 2016 reply Follow Share How to calculate the lower bound for these functions? 0 votes 0 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes https://www.youtube.com/watch?v=gS4Z-fBiOU4 also search for stirling approximaiton viv696 answered Feb 1, 2016 • selected Feb 1, 2016 by nilamd viv696 comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Sourabh Kumar commented May 4, 2016 i edited by Sourabh Kumar May 4, 2016 reply Follow Share n=theta (n/2) then why not 2^n=theta 2^(n/2). I know !n<=nlogn But how can we prove !n<=nlogn please explain.I don't want to prove using strilling approximation –1 votes –1 votes Arjun commented May 4, 2016 reply Follow Share n=theta (n/2)then why not 2^n=theta 2^(n/2). What rule you applied here, I mean how can you take an exponential and still expect result to hold? The first statement is not an "equality" and this is clearly mentioned in asymptotic notation - see Cormen and not some notes. Theta notation just means the growth rate of LHS is same as that of the RHS or the function on LHS belongs to the set of functions whose growth rate is same as that on the RHS. It is not an equality such that we can substitute LHS for RHS at other places. I know !n<=nlogn who told this is true? This is just false and hence can't be proved. n! is just the multiplication of all natural numbers from 1 to n. On RHS we just multiply n with log n. 0 votes 0 votes Sourabh Kumar commented May 5, 2016 i edited by Sourabh Kumar May 5, 2016 reply Follow Share Sorry arjun sir, I actually wanted to write log n!<=nlogn I can prove like this Log n!=log1+log2+........logn (If I replace these terms by higher terms) <=logn+logn+.......logn <=nlogn so I can say that log n!=O(nlogn) And the reason I say 2^n=theta 2^n/2 bcz if we take log both sides Then nlog2=theta n/2log2(if we assume base2) n=theta n/2 –1 votes –1 votes Please log in or register to add a comment.