Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Note that $O(x^{1.5})=O(x^2)$. –  sos440 Mar 30 '12 at 8:22
2  
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
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.