GATE CSE
First time here? Checkout the FAQ!
x
+23 votes
2.4k views

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} )$
asked in Algorithms by (249 points)   | 2.4k views

3 Answers

+34 votes
Best answer
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.
answered by Veteran (13.4k points)  
edited by

@Ahwan There's no need to store the numbers in array. He just means perform a binary search on the range [1, n] for the cube root of n. This is because the cube root of n will always be in the range [1,n]. http://ideone.com/i6lWc6

"..in the worst case we need to do the search O(logn) times".
I am not getting this. In O(logn) time, we get the i for which i^3<=n using binary search.  What will be worst case? Please help
@sks24 It's given that the number n is given in binary, so there are $logn$ bits, naive multiplication will be done in $log^2n$, then $logn$ for the binary search, so I think final complexity should be $O(log^3n)$

EDIT: If we convert the binary to decimal in the beginning, then it will be $O(logn)$
Thanks. Got it.
Thanks.
0 votes

Consider the array of natural numbers .

 00   01   10   11  100  101  110

Suppose we want to find the cube root of $ 6$ , $(n=6)$ to store in binary it takes 3-bits ($ \left \lceil \log_2 n \right \rceil$)

take $m$ as middle element of the array.  (here $m=3$)

step 1 : Find middle element $m$ [ will take $O(1)$ time ]
step 2 : Find cube of m  [ will take $O(1)$ time ]
step 3 : Compare $m^{3} < n$ [ will take $\left \lceil \log_2 n \right \rceil$ time .  We need to compare $\left \lceil \log_2 n \right \rceil$ bits because of binary representation ]
step 4 : If there is match or nothing in array is left we return m else if compared value is grater than $m$ we go left of $m$ else we go right of $m$ loop from step 1

Running Time Complexity Of the Algorithm

  • $\log n$  -> Implementing Binary Search
  • $( \log n )^{k}$ -> Comparing Each bit of the number represented in binary notation where k is the number of loop iterations 
  • So on best case it will take $O(\log n)$ and worst case $O(\log^{k+1} n)$

Example

Iteration 1

  1. $m=3$
  2. $3^{3}=9$
  3. $9 \leq 6$ False we go LEFT of the array [this is compared as $1001\leq 110 $] 

Iteration 2

  1. $m=1$
  2. $1^{3}=1$
  3. $1\leq 6$ True we go RIGHT of the array [this is compared as $01\leq 110 $] 

Iteration 3

  1. $m=2$
  2. $2^{3}=8$
  3. $8\leq 6$ False we go LEFT of the array [this is compared as $1000\leq 110 $] 
  4. Since sonthing in LEFT of the array we return $2$ as it is the nearest cube root

Here we took $O(\log ^{4} n)$

 

[ @arjun sir can u pls check this one ]

answered by Veteran (21.3k points)  
edited by
$k = \log n$ rt?

@arjun sir ,

Actually What i Thought about upperbound complexity $O(\log^{k+1} n)$ is that 

  • Outer Loop  for implementing binary search will take $O( \log n)$ time
  • inner loop for comparing each bit of $n$ for each iteration takes $O( \log n)$ each

Isn't the example correct ?

  1.  $O(\log n) $ for implementing binary search
  2. $O(\log n) $ for comparing bits of 9 and 6
  3. $O(\log n) $ for comparing bits of 1 and 6
  4. $O(\log n) $ for comparing bits of 8 and 6

Here k = number of iterarions . The loop executes for $\log n $ time hence $k=\log n$

Correct me if wrong...

You can count k rt? Also why you taking power and not multiply for getting the time complexity?
Multiplying a number 3 time , is const operation  That is why i took it as $O(1)$
But it varies with the input- not a constant.
See my answer now, there was a mistake which I corrected now.
Got my mistake :)
This is wrong .
@arjun sir complexity will be always $O(\log^{2} n)$  ?  
How does k counted ? will it affect the complexity ?
yes, though I did not prove it. Complexity of multiplying 3 numbers of $\log n$ bits each. Normally we take this as $O(1)$ assuming CPU has a MUL instruction. For this question, we can assume such an instruction is not there.
Such a clear analysis. Thanx a lot sir.
While changing decimal to binary(in 1st case like 9 we will get so we r changing it to binary then comparing with desired binary no .) will not be considered in time complexity??

Just this doubt coming.
0 votes

BY USING LINEAR SEARCH:

algo(n)

{ for(i=1 to n^3)

 if(i^3>n) return(i-1)

}

it takes n^(1/3) time

BY USING BINARY SEARCH:

(1)^3   (2)^3  3  (4)^3  5  6  7  (8)^3  9  10  11  12  13  14  15  (16)^3 ..........

it takes logn time

so c is answer

answered by Loyal (2.9k points)  
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2076 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,649 answers
79,695 comments
31,069 users