# Solve Time Complexity problem using Time Hierarchy

I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use Time Hierarchy.

I need to show that the following are either equal, on inclusive of one another...

TIME($2^{n^2}$) and TIME($n^3 \times 2^n$)

My intuition tells me that...

TIME($n^3 \times 2^n$) $\subset$ TIME($2^{n^2}$)

Can someone explain how I can prove this using the rules of Time Hierarchy?

Your intuition that $\text{TIME}(n^3 \times 2^n) \subsetneq \text{TIME}(2^{n^2})$ is correct.
It is easy to see that $2^{n^2}$ is time-constructible. Given $n$, you can compute $n^2$ in $\log^2 n$ time, then write 100...00 with $n^2$ zeros, in time $O(n^2)$.
The Time-Hierarchy Theorem states that, for such time-constructible $f(n)$,
$$\text{TIME}(o(\frac{f(n)}{\log f(n)})) \subsetneq \text{TIME}(f(n))$$
It is clear that $n^3 \times 2^n \in o(\frac{2^{n^2}}{\log 2^{n^2}}) = o(\frac{2^{n^2}}{n^2})$.
Therefore, $\text{TIME}(n^3 \times 2^n) \subseteq \text{TIME}(o(\frac{2^{n^2}}{\log 2^{n^2}})) \subsetneq \text{TIME}(2^{n^2})$.