Это вернулось к дереву рекурсии.Почему для 1/2 это O(log2(n))?Потому что если n = 2^k, вы должны разделить k раз, чтобы достичь 1.Следовательно, число вычислений составляет не более 1006 * сравнения.Теперь предположим, что это (c-1)/c.Следовательно, если n = (c/(c-1))^k, нам нужно log_{c/(c-1)}(n) операций, чтобы достичь 1.
Теперь, как и для любой константы c > 1, limit log2(n)/log_{c/(c-1)}(n), n \to \infty равно константе, большей нуля, log_{c/(c-1)}(n) = \Theta(log2(n)).Действительно, это можно сказать для любых констант a, b > 1, log_a(n) = \Theta(log_b(n)).Теперь доказательство завершено.