就计算复杂度而言,Big O表示法是O(nlgn)与O(n + nlgn)相同吗？

Question

我正在研究一个问题,我想出了两个算法:一个需要O(n lgn)时间但需要额外的空间,其他需要O(n+nlgn)时间.所以只是想问一下,考虑到最大的价值,O(n lgn)时间复杂性会有所改善,O(n+nlgn)或者两者都被认为是平等的nlgn.

Answer 1

他们是一样的:

n + n lg n <= 2 n lg n   -- for n >= base of logarithm
            = O(n lg n)