# Is log(n) in complexity class P?

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

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

$\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$.
• 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. – Raphael Feb 18 '15 at 8:19