time - 算法的时间复杂度 (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 次。