GATE CS 2003 Q66 — Asymptotic Worst Case Time and Space Complexity

To find the complexity of computing the cube root of $n$, we must analyze the problem in terms of the input size. Let the input $n$ be represented in binary notation.

1. Input and Output Size

• The size of the input $n$ in binary is $L = \Theta(\log n)$ bits.
• The output $m = \lfloor n^{1/3} \rfloor$ has approximately $\frac{1}{3} \log_2 n$ bits. Thus, writing down the output alone requires $\Omega(\log n)$ time.

2. Algorithm Complexity

We can compute $m$ using binary search over the range $[1, 2^{L/3}]$:

1. The binary search takes $O(L) = O(\log n)$ iterations.
2. In each iteration, we perform basic arithmetic operations (multiplication and comparison) on numbers of size at most $L$ bits.
3. Using standard multiplication algorithms, multiplying $L$-bit numbers takes $O(L^2)$ time (or faster, e.g., $O(L \log L)$ using advanced methods).

Thus, the total time complexity is polynomial in the input size $L$, which is $O(L^k) = O((\log n)^k)$ for some constant $k > 0$ (specifically, $k \le 3$).

3. Eliminating Options

• Since the output size is $\Omega(\log n)$, any algorithm must take at least linear time in the input size. Therefore, it cannot run in $O((\log \log n)^m)$ time for any constant $m > 0$. This eliminates Option D.
• Since $O((\log n)^k)$ is strictly more efficient than $O(n^{0.5})$ and $O(n)$, Options A and B are incorrect.

Hence, the complexity is $O((\log n)^k)$ for some constant $k>0$, but not $O( (\log \log n)^m)$ for any constant $m>0$.