The base of the logarithm in estimating the complexity of the nlog(n) algorithm

N

Nodar2014-05-13 20:00:14

Mathematics

Nodar, 2014-05-13 20:00:14

Hello.
I started to learn algorithms, by education not IT in any way.
I can not understand. Let's say BigO for Merge Sort - nlog(n)
What is the base of this logarithm? Natural ln, decimal lg. Unclear.

Reply

Answer the question

In order to leave comments, you need to log in

3 answer(s)

A

Andrey Vershinin, 2014-05-13
@Nodar

Depending on how many parts the array is divided into, this will be the base of the logarithm.

T

throughtheether, 2014-05-13
@throughtheether

One property of this notation is to drop constants before members, as well as lower (less rapidly growing) members. In addition, log[base=a](N)=log[base=b](N)/log[base=b](a), i.e. changing the base of the logarithm effectively changes the constant in front of the corresponding term, which is generally not taken into account ('suppressed') by O-notation.

N

Nodar, 2014-05-13
@Nodar

@WolfdalE
I understand correctly: there is a list [9,4,3,6,8,1]. If, when sorted, it is divisible by 2 [9,4,3] and [6,8,1], then the base of the logarithm is 2. If by 3 [9,4], [3,6], [8,1], then base - 3?