Is binary search’s time complexity log(N) or log base 2 (N)? The USACO Guide says it’s O (log N), but csacademy says its log_2(N). Please let me know!

Thanks!

Is binary search’s time complexity log(N) or log base 2 (N)? The USACO Guide says it’s O (log N), but csacademy says its log_2(N). Please let me know!

Thanks!

Log base 2 n, but with big O notation this is equivalent to log n since they differ by a constant factor.

2 Likes

Usually \log n refers to \log_2n in the context of algorithms anyways.

2 Likes