Сколько бит, как функция n (в форме Θ (·)), требуется для записи числа n 3 в двоичном виде?
Я думаю, что n бит может использоваться для express 2 n различных значений с использованием двоичного двоичного дополнения. Таким образом, на avergae, когда n удваивается, число битов, необходимых для express, увеличивается на 1. Это означает, что n выражается через Θ (log n) битов. Таким образом, подставляя n = n 3 , это Θ (log n 3 ) = Θ (3log n), которое по-прежнему равно Θ (log n).
Если это правильно, есть ли более строгий способ объяснить это? Как насчет n факториала? Я не знаю, как go разобраться с этим.