Skip to main content
latex edit, link wrapper , $log$ to $\log$
Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

In this Wikipedia articleWikipedia 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 \times \log n )$$\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.

In this Wikipedia article 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 \times \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.

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

In http://en.wikipedia.org/wiki/Time_complexity#Polynomial_timethis Wikipedia article 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

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

http://en.wikipedia.org/wiki/Time_complexity#Polynomial_time

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

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

In this Wikipedia article 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 \times \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.

Source Link
Mauricio
  • 326
  • 2
  • 4

http://en.wikipedia.org/wiki/Time_complexity#Polynomial_time

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

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