notation - 根据 n 查找 Theta 表示法

Question

x = x + 1用 n 表示语句在下面的段中执行的次数的 Θ 表示法：

i = 1
while (i < n^2)
    x = x + 1
    i = 3i

我知道它i的增长率为O(3^k)，但我不确定如何Θ获得n.

Answer 1

你必须找出，给定n，你能表演多少次i = 3*i，从i = 1以前开始i >= n^2。您已经知道在k步骤之后，i = 3^k，所以您的任务正在解决

3^(k-1) < n^2 <= 3^k

，即写k为 的函数n。