# Whether the algorithm is polynomial or not with input size which is not polynomial [closed]

A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time.

Is this true or false? and why? any idea?

• The question in the title differs from the question in the body. Which are you interested in? – Yuval Filmus Dec 1 '17 at 7:12
• The answer depends on your model of computation. Which model of computation are you using? Turing machines? RAM machine? C programs? – Yuval Filmus Dec 1 '17 at 7:12

So why does this matter? Writing $k$ units of space generally requires at least $k$ units of time in the contexts where we are interested in doing space analysis. Therefore if the algorithm in fact requires superpolynomial space, it must require superpolynomial time. Additionally, if we cannot prove it doesn’t require superpolynomial space, then it follows that we cannot prove that it doesn’t require superpolynomial time. However, it is possible for us to not be able to prove that it doesn’t require superpolynomial space and in fact requires polynomial time.
Additionally, it’s possible that in your context writing $k$ units of space can be done in much less than $k$ time. There do exist computation models where space is much cheaper than time in this sense, but in those contexts we rarely care about space complexity, because it’s so cheap.