time complexity
63 views
Skip to first unread message
sunidhi arora
Sep 2, 2014, 2:27:16 PM9/2/14
to gate2012...@googlegroups.com
Q : The cube root of a natural number n is defined as the largest natural number m such that (m^3 <= n) . The complexity of computing the cube root of n (n is represented by binary notation) is
(A) O(n) but not O(n^0.5)
(B) O(n^0.5) but not O((log n)^k) for any constant k>0
(C) O((log n)^k) for some constant k>0, but not O( (log logn)^m) for any constant m>0
(D) O( (log logn)^k ) for some constant k > 0.5, but not O( (log log n)^0.5 )
(A) O(n) but not O(n^0.5)
(B) O(n^0.5) but not O((log n)^k) for any constant k>0
(C) O((log n)^k) for some constant k>0, but not O( (log logn)^m) for any constant m>0
(D) O( (log logn)^k ) for some constant k > 0.5, but not O( (log log n)^0.5 )
The ans for this question is option c.
Pls explain this question with example..
Pls ravindra sir..
Reply all
Reply to author
Forward
0 new messages