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

Question

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.

Answer 1

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

Answer 2

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