Нахождение тэта нотации с точки зрения п

Question

Найдите обозначение in в терминах n для числа раз выполнения оператора x = x + 1 в следующем сегменте:

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.