Is Space Complexity of an algorithm linked with memory allocation?

Question

Let us take a simple code snippet running on a computer that iterates over an array

for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        //print (i,j)
    }
}

I understand that int i contributes to Big O(1) whereas array contributes to Big O(array.length) for Space Complexity.

Based on this, Can I estimate how much physical memory is being allocated for the algorithm?

It is not clear what you are asking about? "What really happens" is a question that can be asked about hardware, transistors, memory addressing, wordsize, ... up to the programming language's notion of an array. In relation to space complexity most of this is not relevant, as that is an *order of magnitude* and obviously you need more memory the longer your array is, ...etc. Please focus your question. What is the problem? — trincot, Aug 13 '23 at 14:48
@trincot I tried to precise my question. May I know if it is okay now? — PolamreddyVivekReddy, Aug 20 '23 at 11:43
Yes it's "somehow" connected. But *O(..)* is more a theoretical construct. How much memory is really allocated depends on many things. Machine architecutre, OS, runtime, ... — derpirscher, Aug 20 '23 at 11:51
^^ ... and programming language. Is this Java? Then see [Is there any sizeof-like method in Java?](https://stackoverflow.com/a/2370320/5459839) — trincot, Aug 20 '23 at 11:58
@trincot The link provided by you helps one to understand the memory captured with data structures but my doubt is when we identify the Space Complexity of an algorithm, Can we estimate its physical memory allocation? (Rather than looking at each data structure used in the algorithm) — PolamreddyVivekReddy, Aug 31 '23 at 13:11
Complexity gives an order of magnitude. But unless you know the details of how memory is allocated by a certain configuration (data type, programming language, OS, ...), you cannot estimate more precisely than such order of magnitude. Why do you need it? Can you explain what you want to achieve? — trincot, Aug 31 '23 at 13:15
@trincot When we pen down an application/program, We can already estimate its TC and SC. So, I am trying to understand if SC will help one estimate Physical Memory usage so that one can know the system memory requirements well in advance without actual deployment of the full source code (For example, If we create VDI, how much memory our application could consume approximately) — PolamreddyVivekReddy, Aug 31 '23 at 13:42

score 0 · Accepted Answer · answered Aug 31 '23 at 14:04

From the comments of @trincot @derpirscher & some research here is my answer:

Space Complexity is more of a theoretical construct.

It helps us to understand the trend of memory usage by an algorithm but it is NOT possible to estimate physical memory allocation without actually knowing the configuration of the system (Machine architecture, OS, data type, programming language ...) where the algorithm is being executed.

Is Space Complexity of an algorithm linked with memory allocation?

1 Answers1