The cube root of a natural number n is defined as the largest natural number m…
GATE · 2003 · CS
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)k) for some constant k > 0.5, but not O((log log n)0.5)
Attempted by 115 students.
Sign up free to check your answer
Sign up freeLoading lesson…