Inclusion of computational complexity classes

Question

I am asked to show that $Space(n^5)$ is contained in $Time(n^{n^5})$. I tried doing it from the definitions, but didn't get anywhere. Is there a trick to this? Any help is appreciated.

Answer 1

The trick is the pigeonhole principle. You can show an algorithm using at most $n^5$ space can only be in at most $n^{n^5}$ different configurations and so can only run for that amount of time without entering an infinite loop.