Q66

MCQ2 marks, −0.5

The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq 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 \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} )$

Loading…