6 ms·
That is not entirely true. If you compare two implementations of bubble sort, they will both be O(n^2). Yet one can still be much more efficient than the other.
by Hendrikto 4y ago
That is not entirely true. If you compare two implementations of bubble sort, they will both be O(n^2). Yet one can still be much more efficient than the other.
x^4 and x^10 are both polynomials.
- firechickenbird 4y ago> That is not entirely true what are you referring to? Obviously x^4 != x^10, but noone has ever proven that "if SAT is P, then it would have the lowest (or highest) polynomial complexity among the other problems", or anything similar
- Hendrikto 4y agoI was referring to this: > [All NP-hard problems] have equivalent difficulty. I get what OP meant, but there can still be some NP-hard problems that are more difficult than others. As I said, x^4 and x^10 are both polynomials. I wouldn‘t call them "equivalent" though.