0 0 votes Which of the following represents the running time for run (n) function? O(log n) O(log (log (n)) O(log ∗ (n)) O(n) sombody please provide explanation Algorithms made-easy-test-series algorithms time-complexity + – Pankaj Joshi 1.3k views answer comment Share Follow Print See all 6 Comments 6 6 Comments reply mohit chawla commented Jan 25, 2017 reply Follow flag it is only calling run() with logn value and addition is just constant operation. answer should be c . i.e O(log*n) here * means very small value in terms of n. and recurrence rel is T(n) = T(logn) + c 1 1 replyShare Aboveallplayer commented Jan 25, 2017 reply Follow flag after first logn there is an extra parenthesis...but i am gettiong O(logn) 0 0 replyShare mohit chawla commented Jan 25, 2017 reply Follow flag it would have been O(logn) if we would have been deviding the problem by 2 but here we are dividing it by log(n) and yeah there is extra bracket. like 32/2 = 16 but log32 = 5. therefore ans. should be c. 0 0 replyShare Pankaj Joshi commented Jan 25, 2017 reply Follow flag I understand the reasoning behind log* n but does anybody has any proper mathematical proof 0 0 replyShare Akriti sood commented Jan 25, 2017 reply Follow flag i too think answer should be C. and recurrence should be T(n) =2Tlogn + c..RIGHT?? as two times run(log n) is called. i am not sure of that extra paranthesis 0 0 replyShare Pankaj Joshi commented Jan 25, 2017 reply Follow flag no recurrence should be T(2logn) +c i.e T(logn)+c BTW according to geniouses at made easy answer is O(n) :P 0 0 replyShare Please log in or register to add a comment.
0 0 votes Solving By Back Substitution I am getting O(log n ) bad_engineer answered Jan 25, 2017 bad_engineer comment Share Follow See 1 comment 1 1 comment reply Pankaj Joshi commented Jan 25, 2017 reply Follow flag i don't think it should be log n can you show the steps 0 0 replyShare Please log in or register to add a comment.
