Search code examples
complexity-theory

Does log(n) in programming equivalent to log2(n)?


In binary search since we keep dividing by half the algorithm will be log2(n) but it states that is is log(n) in many sources. Does log(n) in programming equivalent to log2(n)? What is the difference?


Solution

  • Yes, in programming in general, log refers to log2 as it is the most common logarithmic complexity.

    It's also important to note that constants are ignored, so for example 3n and 8n both have complexity O(n), although O(3n) is a bit faster, they will both get slower at same rate. For your example particularly, log2(n) and log9(n) can be both represented as ln(n)/ln(2) and ln(n)/ln(9), therefore, removing constant factors you will get both as ln(n).