Arc Forumnew | comments | leaders | submitlogin
1 point by kens 6008 days ago | link | parent

You're multiplying O(n) numbers, each of which is O(log n) digits long, so the result is O(n log n) digits long.


1 point by shader 6008 days ago | link

Usually, it seems to be either (n log n) or (n log n) - 1 digits.

And usually in this case I would leave of the O, as that usually refers to the performance of an algorithm in time or space. I suppose you could construe the number of digits to be "space" but multiplying O(n) numbers doesn't make that much sense.

-----