Skip to main content
added 323 characters in body
Source Link
gnasher729
  • 31.6k
  • 35
  • 55

For not very large n, log n can be around 20. A factor log n matters about as much as it matters to have a computer built in 2016 and not one built in 1999.

On the other hand, O (n log n) can be faster than O (n) for practical n if the constant factor in the O (n) algorithm is say 50 times larger than for the O (n log n) algorithm.

A factor log n for say n ≥ 100 cannot be ignored if everything else is equal. Sometimes everything else is equal, sometimes it isn't.

For not very large n, log n can be around 20. A factor log n matters about as much as it matters to have a computer built in 2016 and not one built in 1999.

For not very large n, log n can be around 20. A factor log n matters about as much as it matters to have a computer built in 2016 and not one built in 1999.

On the other hand, O (n log n) can be faster than O (n) for practical n if the constant factor in the O (n) algorithm is say 50 times larger than for the O (n log n) algorithm.

A factor log n for say n ≥ 100 cannot be ignored if everything else is equal. Sometimes everything else is equal, sometimes it isn't.

Source Link
gnasher729
  • 31.6k
  • 35
  • 55

For not very large n, log n can be around 20. A factor log n matters about as much as it matters to have a computer built in 2016 and not one built in 1999.