The cube root of a natural number n is defined as the largest natural number m…
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 in binary notation) is:
- A.
O(n) but not O(n0.5)
- B.
O(n0.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 log n)m) for any constant m > 0
- D.
O((log log n)m) for some constant k > 0.5, but not O((log log n)0.5)
Attempted by 63 students.
Show answer & explanation
Correct answer: C
Answer: The cube root can be computed in time polynomial in the bit-length of n, i.e., O((log n)^k) for some constant k > 0, and cannot be done in time bounded by any poly(log log n).
Reasoning:
Let L denote the input length (bit-length) of n, so L ≈ log n.
A simple algorithm: binary search for m between 0 and 2^{⌈L/3⌉}. The number of iterations is O(log m) = O(L).
Each iteration requires computing m^3 and comparing it to n. With m of O(L) bits, naive multiplication costs O(L^2), so computing m^3 costs O(L^2) or O(L^2) per multiplication (two multiplications), i.e., O(L^2) per iteration.
Total cost using naive arithmetic: O(number of iterations × cost per iteration) = O(L × L^2) = O(L^3) = O((log n)^3). Thus the problem is in deterministic polynomial time in log n.
Using faster integer multiplication (Karatsuba, FFT), the exponent k can be reduced; Newton's method gives even faster convergence, but the runtime remains polynomial in L = log n.
Lower bound: any algorithm must read the entire input of L bits, giving a Ω(L) time lower bound. Therefore any bound of the form O((log log n)^m) is impossible.
Conclusion: The complexity is polynomial in log n (O((log n)^k) for some k), and it cannot be bounded by any poly(log log n).