algorithmmemory-managementspace-complexity

Is Space Complexity of an algorithm linked with memory allocation?


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?


Solution

  • 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.