edited by
23,898 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

1 votes
1 votes

Here we  need to find upper and perhaps lower bounds on the complexity of finding an integer cube root m of n. At least one upper bound is trivial, and rules out answers A and B: m can be found in O(log n) time using binary search.

Also note that the input size is O(log n) because the minimum number of bits needed to represent an arbitrary n in binary notation is proportional to log n. Because all bits of the number must be processed to solve the problem, θ(log n) is a lower bound on the time to solve the problem, and therefore the problem cannot be solved in time O((log log n)^w) [where w is some constant > 0] because that isn't O(log n). Thus, answer C applies.

Source:http://www.techtud.com/doubt/gate-2003

0 votes
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 ]

edited by
0 votes
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

0 votes
0 votes
Finding out the largest value of $m$ for the given $n$, such that $m^{3}\leq n$ is a paradigm of Binary search.

How it turns out to be Binary Search

1) Let’s fix what could be the range of values of $m$, i.e $1<=m<=n$

2) Say for some $K$, $K^{3}\leq n$ then the equation also holds for $K-1$(i.e $\left ( K-1 \right )^{3}\leq n$). Since we are looking for larger such $K$, then we start probing the values of $m>=K$.

3) Say, for some $K$, $K^{3}>n$ then the equation also doesn’t hold for $K+1$(i.e $\left ( K+1 \right )^{3}>n$). So we start probing the values of $m<K$.

These three points form the basis for any Binary Search Problem.

At any stage, we are reducing our search space by half.

Total time complexity is $O(logn)$
Answer:

Related questions