patternMajor
Is log(n) in complexity class P?
Viewed 0 times
classcomplexitylog
Problem
$\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.
$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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#39498, answer score: 21
Revisions (0)
No revisions yet.