Menu
Sorry for stupid question. I cannot jog my memory and googling did not help me answer this question.
So basically given a graph G(V,E), I know that O(|V|^2) or O(|E|^2 + |V|^2) is considered to be polynomial complexity, so is O(|E|*|V|) polynomial as well? If not, what kind of complexity is it? I believe it's not pseudo-polynomial either.
Another question is: is O(m*n) considered polynomial as well, given m and n are the sizes of two INDEPENDENT inputs to a problem? I just want to clarify the concept of polynomial time in here and want to know if O(m*n) has a different name for its type of complexity.
668
Yes, O(nlogn) is polynomial time. From http://mathworld.wolfram.com/PolynomialTime.html, An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^m) for some nonnegative integer m, where n is the complexity of the input.
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, that is, T(n) = O(nk) for some positive constant k.
Yes, it is polynomial.
Yes, any constant is a polynomial of degree zero.
it is polynomial O(|V|^3) since the number of edges is bounded O(|V|^2)
130
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
