3
$\begingroup$

$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P?

$n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P?

If not, what complexity classes contain those problems?

The definitions I've found all refer to "polynomial time", not "at most polynomial time". This may be at odds with $\mathcal{O}$ being defined in terms of bounds, but I haven't found a source which clarifies the discrepancy.

$\endgroup$
  • 2
    $\begingroup$ Just modify the algorithm to run longer. $\;$ $\endgroup$ – user12859 Feb 17 '15 at 19:11
  • $\begingroup$ Check the definition of $O$. $\endgroup$ – Raphael Feb 18 '15 at 8:17
18
$\begingroup$

Wikipedia says:

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.

$\mathcal{O}(\log n)$ is upper bounded by $\mathcal{O}(n)$, and $\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ We have to be careful with the term "upper bounded" now. $n$ is not an upper bound of $10^{20} \log n$ in the usual sense, only asymptotically. $\endgroup$ – Raphael Feb 18 '15 at 8:19
  • $\begingroup$ My computer science professor always said that, when it comes to Computer Science, log(n) is a constant. $\endgroup$ – Kalissar Feb 18 '15 at 10:49
  • $\begingroup$ @Kalissar: Quite a large constant, though, which is why hashtables are faster than trees, and sorting is slower than scanning ;-) $\endgroup$ – Steve Jessop Feb 18 '15 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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