Space complexity

Question about Balancing Time and Space


In Space compexity lesson 6/10, Could you please detail the calculus leading to Memory consumption in the following lines:

“Therefore, the space complexity is O(V2 + T) .
With 10,000 32bit values, this will already represent about 400MB of memory. With 100,000 32bit values we need about 38GB of RAM. This is more than most personal computer have.”

Thank you

Hi @matdupas,

The V^2 comes from the fact that we store one sum for each pair of values and V^2 counts the number of pairs we can make out of V values. The T comes from the fact that we need to store a dictionary with one entry for each target.

Regarding the estimation of the MB used: If V = 10000 and each value uses 32 bits, the total number of bits used to store the V^2 sums is:

(10000)^2 \times 32 \ \text{bits} = 3200000000 \ \text{bits}

To convert bits to megabytes you need to divide by 8000000:

3200000000 \ \text{bits} = \frac{3200000000}{8000000} \text{MB} = 400 \ \text{MB}

You can use this google calculator. and replace the 1 by 3200000000, you’ll get 400MB.

Does this answer your question?

Don’t hesitate to ask for a clarification if something isn’t clear.

1 Like

Thank you François, it is very clear.
I get confused between bits and bytes so Thank you

1 Like