GATE CSE 2003 | Question: 66

Question

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} )$

Comments

Answer: C. O((log n)^k) for some constant k > 0

✅ Compact Explanation:

• Input size = log n (binary).

• Use binary search to find largest m such that m^3≤n

• Search range: m∈[0,n] → needs O(log n) iterations.

• Each iteration: compute m^3 and compare with n → takes O((log n)^2) time.

• Total time = O(log n) × O((log n)^2) = O((log n)^3).

---

I tried to simplify it as much as possible

---

Intution :

here we are going to apply two algorithms Binary search and Karatsuba algorithm for bit multiplication... M^3 is monotonically increasing function ,this is the reason we apply binary algorithms .Now m^3≤ n => m≤ n^1/3 that means we m^3 lies between [0,n] so we apply binary search between [0,n] takes logn steps...During each step we are going to calculate m*m*m, (for representing m digit we required logm bits which is equivelent to 1/3logn ) for multiply two logn bits we use Karatsuba algorithm which will takes (logn)^2 times  at each step ... so we have total logn step ....hence total time complexity will be logn * (logn)^2...

Answer 1

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.

Comments

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.

---

@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]

---

I am confused in option C and D

Answer 2

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)

Comments

I think your solution is not perfect.

If I Apply The Substitution Method then TC = O(n^0.33).

How you get O(logn) ? Plz explain.

---

What is the significance of 'n is represented in binary notation'?

---

we've given binary representation of a number this ensuring that atleast $logn$ time we'll take to compute bcz we can reperesnt a number in logn bits @Athira1402

Answer 3

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

Comments

When n shrinks by sqrt time complexity would be O(Log.Log n) and same for the others. Pls check once again.

---

Nitesh Singh 2; 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)$

Answer 4

Option C

Using mcLaurin series

Comments

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

---

This is incorrect, as the series is infinite and can’t be written as $O(ln x)^k$
And note that this is simply expansion for y in terms of x and not the complexity of calculating y from x.

Answer 5

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

Answer 6

The problem asks for the complexity of computing the cube root of n, where n is represented in binary. This means the size of the input is not the value n, but the number of bits required to represent n, which is b=Θ(logn).

The most efficient algorithm for this is to use binary search.

1. The Algorithm: We are looking for the largest integer m such that m3≤n. We can binary search for this value m in the range [1,n].

2. Number of Iterations: A binary search on a range of size n takes O(logn) iterations.

3. Cost of Each Iteration: In each iteration, we take a midpoint mid and compute mid³.

   • The numbers we are dealing with (like mid) can have up to Θ(logn) bits.

   • The cost of multiplying two b-bit numbers is, at worst, O(b2). So, computing mid³ takes O((logn)2) time.

4. Total Time Complexity:

   Total Time=(Number of Iterations)×(Cost per Iteration)

   Total Time=O(logn)×O((logn)2)=O((logn)3)

Evaluating the Options

Our calculated complexity is O((logn)3). Let's see which option this fits.

• A. O(n)...: False. O((logn)3) is much smaller than O(n).

• B. O(n0.5)...: False. O((logn)3) is much smaller than O(n0.5).

• C. O((logn)k) for some constant k>0, but not O((loglogn)m) for any constant m>0:

  • Is our complexity O((logn)k)? Yes, for k=3.

  • Is it "not O((loglogn)m)"? Yes, because (logn)3 grows faster than any power of loglogn.

  • This statement is true.

• D. O((loglogn)k)...: False.

This confirms that C is the correct answer. The key is to analyze the complexity in terms of the number of bits, which leads to a polylogarithmic time complexity.

 

Let's run the algorithm on two examples: a non-perfect cube () and a perfect cube ().

The goal is to find the largest integer m such that .

---

 

Example 1: n = 30

 

Initial state: low = 1, high = 30, answer = 0

Iteration	low	high	mid	mid³	Condition mid³ <= 30?	Action	answer
1	1	30	15	3375	False	high = 14	0
2	1	14	7	343	False	high = 6	0
3	1	6	3	27	True	answer = 3, low = 4	3
4	4	6	5	125	False	high = 4	3
5	4	4	4	64	False	high = 3	3

At this point, low is 4 and high is 3. The condition low <= high is false, so the loop terminates.

The final answer is the last stored value in answer, which is 3. This is correct, as 3^3=27≤30 and 4^3=64>30.

 

---

 

Example 2: n = 27

 

Initial state: low = 1, high = 27, answer = 0

Iteration	low	high	mid	mid³	Condition mid³ <= 27?	Action	answer
1	1	27	14	2744	False	high = 13	0
2	1	13	7	343	False	high = 6	0
3	1	6	3	27	True	answer = 3, low = 4	3
4	4	6	5	125	False	high = 4	3
5	4	4	4	64	False	high = 3	3

Again, the loop terminates because low (4) becomes greater than high (3).

The final answer is 3, which is the correct integer cube root of 27.