18,538 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} )$

The best answer by @gatecse talks about an array. Don’t be confused there is no array in question the reference is used only to make the Visualization of the concept easier.

Eg. finding cube root of 1000, there is no array. So lets try to find out the cube root manually starting from 1, 2, 3, 4……. this will take O(n) time. but since we know the beginning(1) and end(1000) and also logically they are sorted we can make use of binary search concept to get to our answer.

Even if we search for cube root linearly, it should not take more than O(n^0.33) which eliminates option a and b?

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.
by

It must be Θlogn

I believe you mean Ω(log n)

EDIT>> Ah! My bad.. you showed it is already O (log n) above.. fine..

Can you make it more simple ?

What do you ment by this ?
(a[i] * a[i] * a[i] == n).

How it appears to be O( log n ) O(logn)

@Arjun Not understood first paragraph. Why are we doing binary search and of which particular number. We are multiplying cube root of n three times. But from where did we know that this is cube root or not ?
I think since the 1...n are sorted so if we do binary search and if a[i]*a[i]*a[i] is greater than n then we can surely say that cube root is in left side of array and if cube root is less than n then in right side array...
yes. Normally we do $a[i] == x$ in binary search. Here we must do $a[i] \times a[i] \times a[i] == n$. One more thing - if search fails - that is no prefect cube root exist, then the last number being compared should be returned.
Arjun Sir, can you elaborate me about the solution clearly. I can't understand why it is necessary to use binary search instead of linear search
If we use linear search complexity will be $O\left(n^{\frac{1}{3}}\right)$ since we have do do sequential checking from 1 to $n^{\frac{1}{3}}$.
" 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."

How does each bit is important in finding cube root? please explain
Change any bit of a number from 0 to 1 or vice versa. Its cube root also changes. So, every bit is significant in finding the cube root.
Even when k=0.1 or any such small value, answer is correct??? How??
no. Some k>0. Here k must be greater than 1 and k = 2 surely works as shown in answer.
I got it, they have mentioned some constant, i took it as any cconstant. My bad. Thank u sir.

@gatecse. check if a[i]∗a[i]∗a[i]==n). This check takes O(logn) time

how does this check takes O(logn) time??

what if the number n is converted to decimal to find cube root and then find its complexity.will it be wrong to convert the number to decimal?
"We can simply do a binary search in the array of natural numbers from 1..n"
@Arjun sir from where this array comes?

@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.
@Arjun sir. How is it logn^2. It should be logn only? 1...n we do binary search and each time we check a(i)*a(i)*a(i)=n or not and this is a constant time and it will be done logn times at max.Can you tell please how is it logn^2?
@air1

I think final complexity should be O(log3n)O(log3n)

EDIT: If we convert the binary to decimal in the beginning, then it will be O(logn)

Please explain how it becomes O(logn)?
a == b? Usually we consider this as an $O(1)$ operation. But when $a$ is allowed to be arbitrarily large, this can take $O(\log a)$ as each bit needs to be checked. That is why the check is taking $O(\log n)$ in the given question.
Sir in asymptotic analysis we dont bother about how long arithmetic operations take.It depends on h/w .

even when we check a==b in constant as you mentioned,there also a can be any large or small number and we need to check all bit,but we dont bother about that.I still did not get:(
@Arjun sir, why do the binary search on the whole of n elements? Isn't it sufficient to do it only for the 1st n^1/3 elements? If so, then the time taken is also reduced to O(log n^1/3).

cant we do like this?

1) convert given binary representation of $n$ into decimal----$O(logn)$

2) then find $\left \lfloor n^{0.333} \right \rfloor$ --------------$O(1)$

total complexity $O(logn)$

@Arjun sir I have same doubt as above @rahul said.

Do we consider the underlying hardware complexity in asymptotic analysis of our algorithm?

i have the same doubt did u get the answer?
edited
..
How did you get log^2(n) ? I got it we need log(n) for binary search, but why did you square it ?
If  'n'  is not binary number then what is complexity?
If you are wondering how O$(log n)^{2}$ came then see Arjun Sir comment above dated Nov 11, 2017.

and remember we are not converting binary to decimal here so in this method answer would be O$(log n)^{2}$

But if we convert n into decimal first then the time complexity will be reduced to O$(log n)^{}$ which is only the binary search time. But I don't know converting would be appropriate or not.
The number 'n' is represented in 'b' bits. So the cube root will lie in the range of 0 to 2^(ceil(b/3)). So we can do a binary search in this range.
edited

@alpha

Here  the elements are from 1..n  so for every increment in i we have to check that the element present at position i that is a[i] having its cube as n or not.

so there are two ways to do it either we can do it by sequential search or by binary search(if the mid element is having its cube > n then move to left otherwise move to right)

[Note: here we can move right in binary search because we are not sure that we have n sorted natural numbers so any number can be possible]

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).

More simple answer than the previous one.
Small doubt . . . why 2^10 * 2^10 * 2^10 =2^30 which is  (logn)^k. Mot getting this one.

What I meant is if n = 2^30 ,then loop will run for 1025 times, which is (log 2^30)^ 2.038.

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
When n shrinks by sqrt time complexity would be O(Log.Log n) and same for the others. Pls check once again.
edited

; Thanks for pointing it out, this answer is old and stupid as hell.

I'll edit to provide the simplified solution in a while :)

PS: When n shrinks by sqrt, time complexity would be $O(loglogn)$ and not $O(√n)$

Option C

Using mcLaurin series

by

### 1 comment

Good one! So it would take $O((log n)^{k}$) for square root also? (plus extra logn time for binary to decimal conversion)