What's the difference between $t(n^2)$ and $t^2(n)$

Question

Theorem: For every multitape Turing Machine algorithm that takes time $t(n)$, there is an equivalent single tape Turing Machine that takes time $t^2(n)$

I am curious why we say $t^2(n)$ and not $t(n^2)$ and what's the difference.

Thanks!

Answer 1

For some functions $f^2(n)$ = $f(n^2)$, for example $f(n)=n$. However, this is not true for all functions. Take for example: $log(n)$.

$log^2(n)$ is not always equal to $log(n^2)$ for all n. See the chart below:

Answer 2

Assuming you mean quadratic time (please correct me if I'm wrong - I'll fix my answer), I usually see it written $t(n)=O(n^2)$. However, in your case, since $t$ is a polynomial in terms of $n$, we are squaring the actual polynomial, and not the input value (n).

$t(n^2)$ and $t^2(n)$ are different, for example, given the polynomial $t(n)=n^2+1$, we see that $t^2(n)=(n^2+1)^2$, and $t(n^2)=(n^2)^2+1$, so they are clearly different.

Answer 3

There are three places to put the $2$

$t(n^2)$ is unambiguously defined.

$t^2(n)$ could mean $t(t(n))$ or $(t(n))^2$, generally the author makes it clear which is meant.

$t(n)^2$ is not very common but it always seems to mean $(t(n))^2$.