Big Oh Обозначение O ((log n) ^ k) = O (log n)?

Question

В обозначении big-O это O((log n)^k) = O(log n), где k - некоторая постоянная (например, число логарифмических для циклов), верно?

Мой профессор сказал мне, что это утверждение верно,однако он сказал, что это будет доказано позже в курсе.Мне было интересно, может ли кто-нибудь из вас продемонстрировать его действительность или иметь ссылку, по которой я могу подтвердить, если это правда.

Answer 1

(1) Это правда, что O (log (n ^ k)) = O (log n).

(2) Ложно, что O (log ^ k (n)) (также записано O ((log n) ^ k)) = O (log n).

Наблюдение: (1) было доказано Нмджоном.

Упражнение: доказать (2). ( Подсказка: f (n) = log ^ 2 n - это O (log ^ 2 n). Это O (log n)? Какая достаточно большая константа c такая, что для всех n, больших n0, c log n> log ^ 2 n? )

EDIT:

В соответствующей заметке всем, кто посчитает этот вопрос полезным и / или интересным, следует проявить некоторую любовь к новому сайту StackExchange "Информатика". Вот ссылка. Иди, сделай это новое место реальностью!

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

Answer 2

Вы уверены, что он не имел в виду O (log n ^ k), поскольку это равно O (k * log n) = k * O (log n) = O (log n).

Answer 3

O (log n ) - это класс функций.Вы не можете выполнять вычисления, такие как ^ k на нем.Таким образом, термин O (log n ) ^ k даже не выглядит разумным для меня.