What does it mean to find big o notation for memory

Question

I have a question, what does it mean to find the big-o order of the memory required by an algorithm?

Like what's the difference between that and the big o operations?

E.g

a question asks Given the following pseudo-code, with an initialized two dimensional array A, with both dimensions of size n:

for  i <- 1  to  n  do
       for  j <- 1  to  n-i  do
                        A[i][j]=  i + j

Wouldn't the big o notation for memory just be n^2 and the computations also be n^2?

Answer 1

Big-Oh is about how something grows according to something else (technically the limit on how something grows). The most common introductory usage is for the something to be how fast an algorithm runs according to the size of inputs.

There is nothing that says you can't have the something be how much memory is used according to the size of the input.

In your example, since there is a bucket in the array for everything in i and j, the space requirements grow as O(i*j), which is O(n^2)

But if your algorithm was instead keeping track of the largest sum, and not the sums of every number in each array, the runtime complexity would still be O(n^2) while the space complexity would be constant, as the algorithm only ever needs to keep track of current i, current j, current max, and the max being tested.

Answer 2

Big-O order of memory means how does the number of bytes needed to execute the algorithm vary as the number of elements processed increases. In your example, I think the Big-O order is n squared, because the data is stored in a square array of size nxn.

The big-O order of operations means how does the number of calculations needed to execute the algorithm vary as the number of elements processed increases.

Answer 3

Yes you are correct the space and time complexity for the above pseudo code is n^2.

But for the below code the space or memory complexity is 1 and but time complexity is n^2. I usually go by the assignments etc done within the code which gives you the memory complexity.

for i <- 1 to n do

   for  j <- 1  to  n-i  do

                    A[0][0]=  i + j

Answer 4

I honestly never heard of "big O for memory" but I can easily guess it is only loosely relater to the computation time - probably only setting a lower bound.

As an example, it is easy to design an algorithm which uses n^2 memory and n^3 computation, but i think it is impossible to do the other way round - you cannot process n^2 data with n complexity computationally.

Your algorithm has complexity 1/2 * n^ 2, thus O(n^2)