0
$\begingroup$

Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep copy of the data (so now there are two identical versions of the data in memory during execution).

Since B essentially uses twice as much space by copying the data, does it necessarily follow that it will take longer to run? And if so, if two scripts like in the above example do the same thing but arbitrarily take up different amounts of space, what is the relationship between space and and time here?

$\endgroup$

1 Answer 1

1
$\begingroup$

This question seems to have many open ends from my perspective. But here is my take on this.

Firstly, the time complexity would not change since you said the programs do the same computation(feel free to correct me). The time taken to deepcopy would just be something like an initialisation factor and not the actual computation. The running time would increase but whether the time complexity should increase is a problem specific analysis.(For example: A performs linear search and B copies the data and performs linear search. How would you find the time complexity in this case may vary as per your analysis.)

Secondly, you said 2 programs. This means you have 2 independent processes and both of them have their respective copies of data in the memory(ideally).So both of them actually operate on deep copies to begin with and I am assuming by deep copying you mean an explicit copy operation in the program. If they used a shared memory then locking would come into picture and still a copy would mean an explicit copy operation.

Let's assume we have a python script which performs a deepcopy and some operations on it. Yes the running time and space needed for that process would be greater than the one which doesnt copy.

Now assume that you have 2 C programs and in one of them you are creating a copy of the data and assiginig it to a const variable, in such a case the copying would be handled at compile time and there would be no difference in run times.

Using more space doesn't necessary mean the time required would be more. There are many factors affecting it like caches and dedicated hardware for computaion which would help in keeping execution efficient. For example, If one program operates using purely cpu and another one offloads a part of the computation to the gpu, in this case you need to copy data from the main memory to gpu, process it further and return it back to the main memory. These are more tasks but can actually take less time as compared to purely cpu operations.

Hope this gives you some insight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.