GATE 2003

The cube root of a natural number n is defined as the largest natural number m such that (m3≤n) . The complexity of computing the cube root of n (n is represented by binary notation) is

(A) O(n) but not O(n0.5)
(B) O(n0.5) but not O((logn)k) for any constant k>0
(C) O((logn)k) for some constant k>0, but not O((loglogn)m) for any constant m>0
(D) O((loglogn)k) for some constant k>0.5, but not O((loglogn)0.5)

1Comment
Rajeev 10 May 2015 05:26 pm

To answer that question, you need to find upper and perhaps lower bounds on the complexity of finding an integer cube root m of n. At least one upper bound is trivial, and rules out answers A and B: m can be found in O(log n) time using binary search.

Also note that the input size is O(log n) because the minimum number of bits needed to represent an arbitrary n in binary notation is proportional to log n. Because all bits of the number must be processed to solve the problem, θ(log n) is a lower bound on the time to solve the problem, and therefore the problem cannot be solved in time O((log log n)^w) [where w is some constant > 0] because that isn't O(log n). Thus, answer C applies.