Big-O Space requirement for multiplication

Stack Overflow. I see some great resources on time complexity here, but so far I haven't been able to answer to this space complexity question using them. So:

If I am multiplying the first n primes together, what space would be required to store the answer? For example, multiplying the first thousand primes together an开发者_如何学编程d storing the resulting number (an integer, albeit a large one). Would it require n-squared or log(n) space?

Thanks so much!

The prime number theorem tells us that the nth prime is approximately n ln n, so the product of the first n primes is approximately

Π_{i ≤ n}(i ln i) = n! O((log n)ⁿ) = O((n log n)ⁿ)

And to represent this number you'd need space that's the logarithm of that, i.e.

O(n (log n + log log n)).

(Note that this is asymptotically bigger than the space needed to store n!, which is just O(n log n).)

Just taking the last part of your question. If you have a list of the first n primes, the # of digits in the final multiplication will be log(n^n) which is just n log n. Since the algorithm would just be to multiply each one with a single accumulator, i would say the total space requirement would be the final expected # of digits, which is: n log(n)