Is O(log n) the same as O(log 2n)?
2 Answers
By laws of logarithms, log(2N) = log(2) + log(N) and since you are writing it in big O, what you get is O(log(2)) + O(log(N)) = O(log(N).
Yes, O(log n) and O(log 2n) mean the same thing. This is because
log 2n = log 2 + log n,
and since log 2 is a constant, it's ignored by big-O notation.
Going a bit broader than this, properties of logarithms mean that logs of many common expressions end up being equivalent to O(log n). For example, log nk, for any fixed constant k, is O(log n) because
log nk = k log n = O(log n).
Related