This is a worst-case result. In the best case, it is easy to see that the gap can be exponential. Imagine a program that increments a counter until it reaches value n. This "program" would only need O(logn) memory: mainly the counter itself.