# Complexity class P - is $k$ only natural numbers?

I think I have seen an algorithm that has $x^{1.5}$ as its complexity. However, according to Wikipedia, it states that the complexity class P is defined as $\bigcup_{k\in\mathbb{N}} \mbox{DTIME}(n^k)$. So does this mean that only natural numbers are allowed in $k$ in the complexity class P? Or am I mistaken, and there is no algorithm that has rational number as $k$?

Thanks.

-
Note that $O(x^{1.5})=O(x^2)$. –  sos440 Mar 30 '12 at 8:22
I've always thought it was unfortunate that mathematicians used the $=$ sign instead of the $\subset$ or $\in$ sign to indicate that some quantity was $O(f(x))$, but never more so than now. –  MJD Mar 30 '12 at 8:30
Sorry for an ambiguity in that notation. You're right. This bizarre unequality just looks like an ordinary equality, but this kind of usage is so common that it's hard for me to imagine any universal alternative. I know that algebraic number theorists use the notation $x^{1.5}\ll x^2$ and harmonic analysists use $x^{1.5}\lesssim x^2$, but not sure if it is universal also in complexity theory. –  sos440 Mar 30 '12 at 8:43

DTIME($n^{1.5}$) is the class of decision problems solvable by a Turing machine in time $O(n^{1.5})$.

DTIME($n^2$) is the class of decision problems solvable by a Turing machine in time $O(n^2)$.

Any function that is $O(n^{1.5})$ is also $O(n^2)$, so DTIME($n^{1.5}$) is a subset of DTIME($n^2$), and therefore is contained in $P$ as well.

In general, if $f(x)$ is any function at all such that there are $k$ and $n$ with $f(x) < kx^n$ for all sufficiently large $x$, then $f(x)$ is $O(x^n)$, and an algorithm that takes $f(x)$ steps for an input of size $x$ will be in $P$. This includes, for example, algorithms with time complexity $x^e (\log x)^2 + 37x\cos\left(x^2\right) + \hbox{phase of the moon}$.

-

Strictly speaking, you must be careful about notations such as $DTIME(n^{r})$, when $r$ is an arbitrary real number. The reason is that the function $n \rightarrow n^r$ or $n \rightarrow \lfloor n^r \rfloor$ may no longer be computable. (As there are uncountably many reals, but only countably many Turing machines).

-