Mathematics/Logarithm

  1. Logarithms
    1. Definition
      1. Logarithms & Asymptotic Relationships
      2. References
      3. Related
    2. Comments

Logarithms

Definition

A logarithm, is simply an inverse exponential function, that states...

Given...

$b^{x}\; =\; y$

Then...

$x\; =\; \log _{b}y$

Logarithms & Asymptotic Relationships

Given...

$c^{\log _{c}x}\; =\; x$

And asymptotically (which means Big-O notation and friends), the base of a logarithm does not matter...

$\log _{b}n\; =\; \frac{\log _{c}n}{\log _{c}b}$

Note that n is our variable here, and so the denominator on the RHS is simply a constant, hence the asymptotic indifference; i.e., LHS = k ⋅ RHS, where k is some constant.

Finally,

$\log _{c}n^{\alpha }\; =\; \alpha \cdot \log _{c}n$

...This is very powerful! What it shows is how logarithms can crumble the complexity of polynomials, any polynomial! For example, there is a huge difference in complexity between n2, and n473, but the complexity of their logarithms is asymptotically identical!

References

  • The reference MyReferenceBook1 is not available: To add this reference (book/uri) simply email <ai at autonomy dot net dot au> with details, and your book will be added. See the references page for details.

  •  <<<— REFERENCE: Do not delete this until you have completed referencing of this page —>>> 

Ancestors ☣ Agent ➢ Agent
Siblings ☣ Agent/ModelBased/UtilityBased
Opposite ☣ Agent/ModelBased/UtilityBased
Other ☣ Algorithm/Learning/TDL/QLearning

Comments

Add comment