Your answer sounds like the solution to the mutable data question, not the pure/impure question.
For the question of memory usage on a lazy language vs a strict language, there is no asymptotic difference. The strict program can be viewed as a series of commands, each modifying the state of the program. For example, consider the following code:
int double(int x){
int ans=x;
ans=ans2;
return ans;
}
The above code can be viewed as:
Input state | execute(ans=x) | execute(ans=2x) | execute(return ans)
where execute takes as an input both the state of the program, and a command. (As an aside, this is the approach of piping a state variable across functions is how Haskell handles IO)
The above code can also be viewed as:
Input | A(x) | B(x) | C(x)
Evaluating this lazily will get you:
C . B . A . Input
What the program wants to return is the final output of C. When the program tries to return C, it will go down the chain of expressions it must evaluate until it reaches one that it can, in this case A(Input). Once A(Input) is calculated, we no longer need Input it memory, so it can be garbage collected. At this point, the program is:
C . B . Input'
Because Input' is the same size in memory as Input, we are, at this point, using no more memory than the strict version of the program. We can continue this argument until we eventually arrive at the final state, in which we have our answer.
With this, we can see that any strictly evaluated program can be done lazily with no more than twice the memory requirements (there is a point where we need both Input, and Input'), which from an asymptotic standpoint is equvilent.
The above code can also be viewed as: Input | A(x) | B(x) | C(x)
Evaluating this lazily will get you: C . B . A . Input
What the program wants to return is the final output of C. When the program tries to return C, it will go down the chain of expressions it must evaluate until it reaches one that it can, in this case A(Input). Once A(Input) is calculated, we no longer need Input it memory, so it can be garbage collected. At this point, the program is: C . B . Input' Because Input' is the same size in memory as Input, we are, at this point, using no more memory than the strict version of the program. We can continue this argument until we eventually arrive at the final state, in which we have our answer.
With this, we can see that any strictly evaluated program can be done lazily with no more than twice the memory requirements (there is a point where we need both Input, and Input'), which from an asymptotic standpoint is equvilent.