1 votes 1 votes which of the following estimates are true? Explain with valid reasons. a) (2n)! is theta (n)! b) log((2n)!) is theta (log(n)!) Algorithms asymptotic-notation algorithms + – AIkiran01 asked Jul 14, 2018 AIkiran01 1.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes a) false b) true abhishekmehta4u answered Jul 14, 2018 abhishekmehta4u comment Share Follow See all 10 Comments See all 10 10 Comments reply AIkiran01 commented Jul 14, 2018 reply Follow Share in (b) part when you split 2n log( 2n )=2n log(2)+ n log(n) shouldn't it be 2n log( 2n )=2n log(2)+ 2nl og(n) 1 votes 1 votes abhishekmehta4u commented Jul 14, 2018 reply Follow Share Yes u r right 0 votes 0 votes Mayankprakash commented Jul 14, 2018 reply Follow Share @Abhisekh Nicely explained. I have some doubts please suggest. 1.how you wrote 2n! To the 2n^2n. 2.In first part,can I tell n! = O(2n)! And how to write the relation between big oh and big omega .I get stuck in these type of questions as how to convert it into big oh,big omega and big thetha. Thanks 0 votes 0 votes Shubham Shukla 6 commented Jul 15, 2018 reply Follow Share @abhishek mehta in second part f(n)=2nlog2+2nlogn g(n)=nlogn so if u cancelcommon term f(n) is still greater by n how you wrote theta isnt that wrong buddy..? 0 votes 0 votes Shubham Shukla 6 commented Jul 15, 2018 i edited by Shubham Shukla 6 Jul 15, 2018 reply Follow Share @mayanprakash (2n)!=(2n)(2n-1)(2n-2)............................(2n-2n)(total 2n terms) for worst case we can consider each term as 2n as we are giving upper bound for value, so u can write as=(2n)^2n and yes you can write n!=O((2n)!) as proved above Look big O you can write when you are giving a max bound for some exprsn like for example we gave for (2n)!=2n^2n=O(2n^2n) If for some exprsn we are giving lower bound it means that for this exprsn in any possible case its minimum value cant go below beyond this value..... same can be said for Big O just changing minimum to maximum in above line. Now theta,you can write theta between two funcs only when they differ by constant values like for exmple f(n)=100000000000n g(n)=n here u can write as f(n)=Theta(g(n)) 1 votes 1 votes abhishekmehta4u commented Jul 15, 2018 reply Follow Share @subham F(n)=n+nlogn G(n)=nlogn Can i say F(n)=O(G(n)) ??? 0 votes 0 votes Shubham Shukla 6 commented Jul 15, 2018 reply Follow Share @abhishek mehta no you cant say because f(n) is greater by n than g(n).. 1 votes 1 votes Mayankprakash commented Jul 15, 2018 reply Follow Share @shubham To the previous reply of Abhishek can I tell f(n) = omega(g(n)) as g(n) is lower bound or smaller to f(n)? Thanks 0 votes 0 votes Shubham Shukla 6 commented Jul 15, 2018 reply Follow Share @mayanprakash yes that you can say..! 1 votes 1 votes harishrajora commented Jul 17, 2018 reply Follow Share Can anyone specify any particular source or pdf or anything by which it is mentioned how to solve these type of questions? 0 votes 0 votes Please log in or register to add a comment.