10
$\begingroup$

What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?

$\endgroup$

migrated from math.stackexchange.com Jul 28 '12 at 2:07

This question came from our site for people studying math at any level and professionals in related fields.

  • 2
    $\begingroup$ What have you tried? Which machine and cost model do you assume? $\endgroup$ – Raphael Jul 28 '12 at 11:06
12
$\begingroup$

By using the fast Fourier transform, multiplications on $k$-bit numbers can be done in time $\tilde{O}(k)$ (where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute $n^{n^2}$ with $O(\log n)$ multiplications, and each multiplication involves no number larger than $n^{n^2}$, which has roughly $n^2 \log_2 n$ bits. So the total amount of time required is $\tilde{O}(n^2(\log n)^2)=\tilde{O}(n^2)$.

$\endgroup$
3
$\begingroup$

Edited in response to comments The time to compute $f(n) = n^{n^2}$ can be decomposed into the time required to compute $f_1(n) = n^2$ and that required to perform $n ^ {f_1(n)}$. I'll assume that multiplying an $m$ bit number by an $n$ bit number takes exactly $mn$ time by the school book method ; additions, etc. are constant time. As a result, computing $n^2$ takes $\log_2^2 (n)$ time.

Suppose that we use binary exponentiation for computing $f(n)$. Binary exponentiation does two kinds of operations in computing $f(n)$: squaring the current product, and multiplying the current product by $n$, according to whether the current bit in the binary expansion of $n^2$ is 0 or 1. In the worst case, $n^2$ is a power of two, so that binary exponentiation repeatedly squares its current product until it reaches the answer.Note that $n^2$ has $m'=\lceil 2 \log_2(n) \rceil $ bits, so that the number of such squarings is $m= m'-1$. This is the case we analyze further below.

The first squaring takes $t_1=\log_2^2(n)$ time, resulting in a $o_1=2 \log_2(n)$-bit product . The second squaring takes in two $o_1$ bit numbers and runs in $t_2=o_1^2$ time, resulting in a $o_2=2o_1$-bit product. Continuing, the $i$-th step takes $t_i = 4^{i-1}\log^2_2 n$ time and outputs a $o_i=2^{i} \log_2 (n)$ -bit product. This process stops at the $m$-th step; as a result, it takes time

$T _{exp} =\sum _{[1..m]} t_i = \log_2 ^2 (n) \sum_{[1..m]} 4^i = \frac{4^m -1} {3} \log_2 ^2 n$.

When the initial squaring cost is included, we find we need time at most

${T_{exp} + \log_2^2{n}}$

Note

  • I omitted some floors and ceilings in the computations, hoping they would not materially affect the answer.
  • I deliberately omitted an $O$-based analysis in favour of an exact upper bound just to be rigorous.
  • The above reasoning also makes clear why my earlier analysis was flawed. The $O$ notation was used in a fast-and-loose way, and it conveniently omitted constants so that, for instance, $\sum t_i $ magically became $O(\log n)$.
  • The multiplications can be always speeded up by FFT and other methods.
$\endgroup$
  • 1
    $\begingroup$ How have you got $\mathcal{O}(1)$ complexity for computation of $n^{2}$? $\endgroup$ – Shaktal Jul 27 '12 at 19:31
  • 4
    $\begingroup$ I'm you're going to say that multiplication of two $n$-bit numbers takes $O(\log n)$ time instead of $O(1)$ time, you need to figure that into the cost of the binary exponentiation also. $\endgroup$ – Mark Dominus Jul 27 '12 at 19:35
  • 2
    $\begingroup$ Note that the final result has $n^2\log_2 n$ bits. It's very hard to compute $n^2\log_2 n$ bits in $O(\log n)$ time. $\endgroup$ – Thomas Andrews Jul 27 '12 at 19:36
  • $\begingroup$ Fair point, I'll take note $\endgroup$ – PKG Jul 27 '12 at 19:39
  • 1
    $\begingroup$ @ThomasAndrews: That depends on the machine and cost model. It is not unusual to assume a RAM model with contant cost for additions. $\endgroup$ – Raphael Jul 28 '12 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy