1
$\begingroup$

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!

$\endgroup$
1
  • 4
    $\begingroup$ They are different, $t^2(n)$ means $(t(n))^2$, the square of $t(n)$. $\endgroup$ Oct 1, 2015 at 0:05

3 Answers 3

2
$\begingroup$

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:

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Shouldn't it be (log n^2) not (log 2n) ? $\endgroup$ Oct 1, 2015 at 1:00
  • $\begingroup$ @MarkWright, you are correct, I should fix this-Thx. $\endgroup$
    – NoChance
    Oct 1, 2015 at 1:02
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .