edited by
23,900 views
106 votes
106 votes

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 

  1. $O(n)$ but not $O(n^{0.5})$
  2. $O(n^{0.5})$ but not $O((\log n)^k)$ for any constant $k>0$
  3. $O((\log n)^k)$ for some constant $k>0$, but not $O( (\log \log n)^m)$ for any constant $m>0$
  4. $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$
edited by

8 Answers

Best answer
113 votes
113 votes
We can simply do a binary search in the array of natural numbers from $1..n$ and check if the cube of the number matches $n$ (i.e., check if $a[i] * a[i] * a[i] == n$). This check takes $O(\log n)$ time and in the worst case we need to do the search $O(\log n)$ times. So, in this way we can find the cube root in $O(\log^2 n)$. So, options (A) and (B) are wrong.

Now, a number is represented in binary using $\log n$ bit. Since each bit is important in finding the cube root, any cube root finding algorithm must examine each bit at least once. This ensures that complexity of cube root finding algorithm cannot be lower than $\log n$. (It must be $\Omega \left( \log n \right)$). So,  (D) is also false and (C) is the correct answer.
edited by
73 votes
73 votes

Consider the below function:

int cuberoot(int n)
{
    int crt;
    for(int i =1; i<=n;i++)
    {
    if (i*i*i<=n)  crt=i;
    else return(crt);
    }
}

The above function will return the cube root of value 'n' as defined in question.

Now if n = 64, the for loop will run 5 times(i=1,2,3,4,5) O(logn).

But if we take larger value say n= 2^30 then the for loop will run (2^10 +1=1025)  times (since 2^10 * 2^10 * 2^10 =2^30) which is  (logn)^k , where k=2.038.

Therefore we can say that the complexity of computing cuberoot  will O((logn)^k) but not O(loglogn).

Hence Answer is (C)

edited by
14 votes
14 votes

EDITED:-

See, if we have all the numbers in a sorted fashion in an array, we can use binary search which takes $O(logn)$ time.

So, the time complexities mentioned in Options A and B hold. The "but not" part makes these options wrong.

The question says that 

n is represented by binary notation

Hence the size of each number is $O(logn)$.

When performing the binary search, all the $O(logn)$ bits of a number would be potentially checked to find a match. Hence, at the minimum this algorithm would take $O(logn*logn)$ time = $O(logn)^2$

Since this would be the minimum time, we can't get $O(loglogn)$, hence Option D is incorrect, too.

 

Option C

edited by
10 votes
10 votes

Option C

Using mcLaurin series

Answer:

Related questions