У меня есть метод:
while (i<k) {
i = i * k
}
Я знаю, что это O(logkn) сложность времени (и это легко продемонстрировать на примерах), но я не понимаю, как мы на самом деле получаем это, используя определение O(g(n)):
Мы говорим f(n) имеет временную сложность O(g(n)), если существует постоянная c > 0, n0 >=1, которая f(n) <= c*g(n).
В нашем случае, как мы находим g(n) = logkn?