Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Just curious, what would be the computational complexity of computing $3^{n^n}$?

I am not sure what it would be like.

share|improve this question
1  
It base 3, it is fairly easy. :) –  Thomas Andrews Nov 6 '12 at 6:29
    
I am curious $3^{n^n}$ means $(3^n)^n$, right? –  Patrick Li Nov 6 '12 at 6:33
    
yes. you are right. –  lovers Nov 6 '12 at 6:35
1  
I'm confused. I thought $(3^n)^n$ is $3^{n^2}$. –  EuYu Nov 6 '12 at 6:54
2  
Usually $3^{n^n}$ is taken to mean $3^{(n^n)}$. Now, what model of computation are you using? –  Robert Israel Nov 6 '12 at 7:03
show 4 more comments

3 Answers 3

If I understand what it means.

The problem is it gets huge each time like the sequence is

$< 3, 81, 19683, 43046721,\ldots >$

The number of digits of the $n$th term is $\lceil n^n\log_{10}3\rceil$. So, $5$th and $6$th term has $1492$ and $22261$ digits respectively.

The $7$th, $8$th and $9$th term has $392930$, $8004767$ and $184846559$ digits respectively.

And $10^{10}$ has $11$ digits itself.

share|improve this answer
add comment

For simplicity, I will first assume that you are adopting a computational model that only keeps track of the number of multiplications (and that multiplication can be done in time independent of the number of integers).

We may then compute $3,3^2,(3^2)^2,\ldots, 3^{(2^n)}$ with $0,1,\ldots, n-1$ multiplications, respectively. As any number less than $2^{n+1}$ is a sum of terms in $\{1,2,\ldots, 2^n\}$, it suffices in the calculation of $3^{n^n}$ to first calculate $3^{2^j}$ for $j \leq \lfloor n \log_2 n\rfloor$, and then take a product of at most $\lfloor n \log_2 n \rfloor +1$ of these $3^{2^j}$ terms. To perform these preliminary calculations takes $\lfloor n \log_2 n \rfloor$ operations, and to multiply the end results requires another $\lfloor n\log_2 n \rfloor +1$ multiplications. We then conclude in time $\sim 2n \log_2 n$.

Of course, this first answer is silly because the time required to multiply integers depends heavily on the length. In fact, to merely output our answer requires time $O(n^n)$, as $3^{n^n}$ has $O(n^n)$-digits.

Now, let's assume it takes time at most $O(f(n))$ to square an $n$-digit number. Then calculation of $3^{2^i} \times 3^{2^i}=3^{2^{i+1}}$ takes time $O(f(2^i))$, and so we can compute $3^{2^j}$ for $j \leq \lfloor n \log_n n\rfloor$ in time $$ O\left(\sum_{j=1}^{\lfloor n \log_2 n \rfloor} f(2^j)\right).$$ For $f(n)= n\log n \log \log n$ (see here), this gives a total time of $$\sum_{j=1}^{\lfloor n \log_2 n\rfloor}O(2^i \log 2^i \log \log 2^i)=\sum_{j=1}^{\lfloor n \log_2 n\rfloor}O(2^i i\log i)=O(n^{n+1}\log^2 n),$$ using comparison with an integral and some Mathematica magic. This is quite reasonable, as we have already seen that the lower bound $O(n^n)$ must hold.

In general, one rarely obtains "exact" growth orders for the computational complexity of even simple algorithms (e.g. multiplication).

share|improve this answer
add comment

Let $M(n)$ denote the complexity of the multiplication of two integer with $n$-digits (let say in base two). Thanks to Schonhage and Strassen we know that $M(n) = O(n \log n \log\log n)$. Thanks to Fürer, we even know that it's a bit lower.

Let $a$ be an integer and $b$ an integer. Then $a^b$ can be computed in time $O(M(b \log_2 a))$ using fast exponentiation. This is not bad: since $a^b$ has bit-size exactly $b\log_2 a$, the cost of the computation is almost the size of the output.

So the complexity of computing $a^{b^c}$ is the cost of computing of $b^c$ plus the cost of computing $a^{b^c}$. When $a$ is at least 2, then the second operation dominate the first, and the total cost is $O(M(b^c \log_2 a))$.

We could make explicit the constant in the big-oh, and we would realize that is is not much larger than 2 or 3.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.