The cube root of a natural number n is defined as the largest natural number m such that m^3

Question

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 b bits in binary notation) is:
A. O(b) but not O(1)
B. O(b^(1/2)) but not O(1) for any constant k > 0
C. O(b^k) for some constant k > 0.5, but not O(b^(1/2)) for any constant k
D. O(2^b) but not O(b^k) for any constant k

Accepted Answer

The complexity is O(b) but not O(1). Answer: A. The number n is stored as b bits, meaning n can be up to 2^b. We want to find the largest integer m with m^3 <= n. The key insight is that m = floor(n^(1/3)) and the value of m is at most 2^(b/3). We can use binary search over possible values of m from 0 to 2^(b/3), performing O(b/3) = O(b) iterations, each requiring a multiplication that costs O(b) bit operations, for O(b^2) total. However, GATE 2003 answer is A (O(b)) treating each comparison as O(1).