O (log n) уточнение

Question

Есть множество вопросов вокруг O(log n) и что это на самом деле означает, не пытаясь открыть это снова.

Однако на этот конкретный ответ https://stackoverflow.com/a/36877205/10894153, это изображение не имеет смысла для меня:

При этом, учитывая, что за этот ответ набрано более 100 голосов, и он уже более 2 лет, и никаких комментариев, указывающих на то, что что-то может быть не так, я предполагаю, что я что-то неправильно понимаю, поэтому прошу дать разъяснения (и Я не могу оставлять комментарии из-за низкой репутации).

В основном, я не понимаю, почему O(log(n)) равно 10, когда n == 1024. Разве это не должно быть 32, считая 32^2 = 1024?

Очевидно, что это влияет и на O(n * log(n)), но просто нужно понять, почему O(log(1024)) = 10

Answer 1

Таблица верна, за исключением того, что заголовки могут вводить в заблуждение, потому что значения ниже их соответствуют выражениям внутри big-O, а не самим big-O. Но это понятно, потому что О-нотации имеют значение игнорирования мультипликативных констант.

Нечто подобное происходит и с log(n). Обозначение log также означает игнорирование base логарифмической функции. Но это нормально в этом контексте, потому что:

log_b(n) = log_2(n)/log_2(b)                 ; see below why this is true

означает, что функция log_b() является просто мультипликативной константой , а именно 1/log_2(b), из log_2().

И поскольку в таблице специально подчеркивается тот факт, что в записи big-O игнорируются мультипликативные константы, можно предположить, что все записи в ней основаны на 2.

В частности, O(log(1024)) можно интерпретировать как log_2(1024), что является ничем иным, как 10 (потому что 2^10 = 1024).

---

Чтобы проверить приведенное выше уравнение, нам нужно проверить, что

log_2(n) = log_2(b)log_b(n)

По определению log мы должны видеть, что n равно 2 с правой стороны, т.е.

n = 2^{log_2(b)log_b(n)}

но правая сторона

{2^{log_2(b)}}^{log_b(n)} = b^{log_b(n)} = n

снова по определению (применяется дважды).