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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Just modify the algorithm to run longer. $\;$ $\endgroup$
    – user12859
    Commented Feb 17, 2015 at 19:11
  • $\begingroup$ Check the definition of $O$. $\endgroup$
    – Raphael
    Commented Feb 18, 2015 at 8:17

1 Answer 1

Reset to default
21
$\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$.

Improve this answer
$\endgroup$
3
  • 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
    Commented Feb 18, 2015 at 8:19
  • $\begingroup$ My computer science professor always said that, when it comes to Computer Science, log(n) is a constant. $\endgroup$
    – Kalissar
    Commented Feb 18, 2015 at 10:49
  • 1
    $\begingroup$ @Kalissar: Quite a large constant, though, which is why hashtables are faster than trees, and sorting is slower than scanning ;-) $\endgroup$
    – Steve Jessop
    Commented Feb 18, 2015 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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