2
$\begingroup$

I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we increase n by one bit, so the algorithm computing n^n has exponential computational complexity?

Second question, what is the computational complexity with respect to n of operations on the result n^n, such as multiplying n^n by a number of similar size?

n can be a large number, so I guess multiplication should not be considered O(1), am I wrong?

$\endgroup$
1
$\begingroup$

Let M(x) be the time needed to calculate the product of two x-but numbers. n^n is a number with n log n bits. Calculating n^n using repeated squaring, the last product takes M(n log n). All the earlier products needed take M(n/2 log n), M(n/4 log n) etc, and this sums up to roughly 2 M(n log n). A bit more, because we’ll need some multiplications by n, which are quite fast.

So roughly 2 M(n log n), and M(x) is O(x log x), so O(n log^2 n). There may be some small corrections needed.

$\endgroup$

Your Answer

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

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