logarithm

Related:

---

Math is Fun

How many of one number multiply together to make another number ?

Example from Math is Fun¹

How many 2’s multiply together to make 8 ?

2 x 2 x 2 = 8

so we need three 2’s to get a product of 8

we’d write it as the following

${\log }_2(8)=3$

key terms

• base: number we multiply (example: 2)
• logarithm: how often the base needs to be multiplied (example: 3)
• the desired number (example: 8)

Common logarithm (log) are base 10. If they’re base 10, they don’t need to precise the base number

natural logarithms have a base e, also known as Euler’s number

computer science - algorithms and logs

dichot (Binary Search)
Time Complexity: $O(logn)$
Quick Explanation: This algorithm repeatedly divides the search interval in half, leading to logarithmic time complexity.
Detailed explanation:

• the code has one loop
• each iteration of the loop results in the vector length being cut in half
  • using logarithm, this can be expressed as ${\log }_2(n)$ = how many times I can divide by 2 before getting to 1
  • where $n$ are the number of elements in a vector pool
• the reason why it’s defined as $log(n)$ and not ${\log }_2(n)$ is because in computer science log usually means ${\log }_2$ ¹ due to ignoring constant factors
  • so if the algorithm divides the problem by 2, 3, or 10 at each step, the growth characteristic is still logarithmic[^2]
• so time complexity of this algorithm in $Olog(n)$

References

Footnotes

1. Introduction to Logarithms ↩ ↩²