3 ms·
I disagree. The array is stored outside of your algorithm. The algorithm is constant space.
by alexchamberlain 15y ago
I disagree. The array is stored outside of your algorithm. The algorithm is constant space.
- JoachimSchipper 15y agoAt least the sum needs ~log(N^2) bits. We typically assume that stuff fits in the native word size and thus takes a single cycle independent of the actual length of the number, but that's obviously not actually true (for numbers >= 2^32 or 2^64, etc.)
- IsTom 15y agoYou still need to read O(nlogn) bits of the array. It can't take less than O(nlogn) time.