大O分析日志^2与线性

Question

对于相当多的元素n，哪一个通常被认为更好？O(n)还是O(log^2(n))？

Answer 1

无论k有多高，O(log^k(n))都是O(n)的下界。它仍然是"亚线性"的。当然，这与"更好"不是一回事；渐近复杂度只是优化难题的一部分。