3. Space efficiency / complexity

Space efficiency is a measure of how much memory (space) the algorithm takes as its input (N) is scaled up.

It has two parts. There is the space taken up by code as N is increased and there is the space taken up by data as N is increased

We could add up the first three natural numbers with three lines of code:-

              x = 1

              x = x + 1

              x = x + 1

The data space is fixed (it is always x), and this code takes three lines. Now if we want to add the first four numbers an extra line of code would be needed, and if a million was to be summed, then a million lines of code would be needed.

Therefore with this algorithm, space increases linearly with N.

Of course this would be a silly way to add up numbers, but it shows that efficient coding has a direct effect on space efficiency.

An alternative to writing down line after line of summing, would be to use a loop

           For x = 1 to N
               x = x + 1
           Next x 

Now the code space is constant as it does not depend on N. N could be a million and yet these three lines of code can deal with it.

The data space is also constant as there is no dependency on N. The only data space used is for the variable x.

This explains why loops are so popular in coding an algorithm - they are very space efficient.

Loops are used to improve space complexity, but of course each iteration of the loop takes time - therefore using a loop does not improve time complexity.

Some problems cannot be solved with constant space complexity, for example creating an algorithm to deal with video in a certain way - as the video becomes longer, then memory requirement also goes up.