Основание логарифма при оценке сложности алгоритма nlog(n)

Question

[Нодар]

Привет.
Начал учить алгоритмы, по образованию не IT никак.
Не могу понять. Допустим BigO для Merge Sort - nlog(n)
Какое основание у этого логарифма? Натуральный ln, десятичный lg. Непонятно.

Answer 1

[Андрей Вершинин]

Зависит от того, на сколько частей делится массив, это и будет основанием логарифма.

Answer 2

[throughtheether]

Одно из свойств этой нотации - отбрасывание констант перед членами, а также младших (менее быстро растущих) членов. Кроме того, log[base=a](N)=log[base=b](N)/log[base=b](a), т.е. при смене основания логарифма эффективно меняется константа перед соответствующим членом, что в целом не учитывается ('подавляется') О-нотацией.

Answer 3

[Нодар]

@WolfdalE
Правильно понимаю: есть список [9,4,3,6,8,1]. Если при сортировке он делится на 2 [9,4,3] и [6,8,1], то основание логарифма 2. Если на 3 [9,4], [3,6], [8,1], то основание - 3?

Comments

[Андрей Вершинин]

Верно.

[Нодар]

Спасибо

[Андрей Вершинин]

@Nodar Ну и отсутствие здесь основания исходит из теории алгоритмов - тык