这个问题的时间复杂度“渐近运行时间差异：O(nlogn) vs O(n) 使用主定理

Question

考虑以下过程，该过程将数组 A 作为输入。 printStuff 子例程的渐近运行时间？

（https://i.sstatic.net/kSjZ5Eb8.png）

这里我已经完成了正常的方法一步一步的计算，我得到了 O(nlogn) 但在使用主方法时我得到了 O(n) 那么正确的答案是什么

Answer 1

它是 O( n log n ) 原因如下：

如果我们像这样删除第 7,8 行：

肯定是 O(n)

但是有一个额外的部分，它每次都会减慢函数的速度， 这需要 O(log n) 所以我们将它们相乘，它将是：

O(n log n)