Merge pull request cp-algorithms#1568 from harsh-1806/correction/fix-log-base-2

mhayter · web-flow · commit 7b91d9cc915f · 2025-11-29T12:05:50.000-05:00
correct log n base 2 instead of 2 log n
diff --git a/src/algebra/binary-exp.md b/src/algebra/binary-exp.md
@@ -29,7 +29,7 @@ Let's write $n$ in base 2, for example:
 
 $$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$
 
-Since the number $n$ has exactly $\lfloor \log_2 n \rfloor + 1$ digits in base 2, we only need to perform $O(\log n)$ multiplications, if we know the powers $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log n \rfloor}}$.
+Since the number $n$ has exactly $\lfloor \log_2 n \rfloor + 1$ digits in base 2, we only need to perform $O(\log n)$ multiplications, if we know the powers $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$.
 
 So we only need to know a fast way to compute those.
 Luckily this is very easy, since an element in the sequence is just the square of the previous element.
