算法的时间复杂度（Big O，Omega）

Question

我试图更好地理解时间复杂度，我希望有人能帮助我计算出以下算法（伪代码）在最坏情况下的时间复杂度：

for i= 0 to n−1:
    if A[i] < 0:
        b= 1
        while b < n:
           b=b×2
    end while
  end if
end for

Answer 1

提示：

内部循环执行了 Θ(log n) 次 - 当它被执行时 - 因为它在 b 的位数与 n 一样多时退出。

现在最坏的情况是A[i]全部为负，所以内循环执行n次

Time complexity of algorithm (Big O, Omega)