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?