Functions

Summary

Input → output machines

Factorial

The factorial $n!$ can be defined as ${\prod }_{x=1}^{n}x=1\cdot 2\cdot 3\cdot \dots \cdot n$ or recursively…
$n!=n\cdot \left(n-1\right)!$

Fibonacci Numbers

These are numbers where the next number in the sequence is the sum of the previous two. This can be defined recursively $f\left(n\right)=f\left(n-1\right)+f\left(n-2\right)$. There is also a closed form definition called Binet’s formula.

Logarithms

Note

This is an operator I kind of just take for granted but I can’t say I’ve really understood what it meant until now.

According to the definition of the logarithm, ${\log }_k\left(x\right)=a$ exactly when $k^a=x$ (exponentials negate logarithms). What this means, is that ${\log }_k\left(x\right)$ is the number of times we need to divide x by k before we reach the number 1. Logarithms are used in the analysis of algorithms because many efficient algorithms halve something at each step. Hence, we can estimate the efficiency of algorithms using logs.

There are also various log rules that are useful here to manipulate logaithms:

• Log of product
• Log of exponents
• Log of quotient
• Log of ratios (${\log }_u\left(x\right)=\frac{{\log }_k\left(x\right)}{{\log }_k\left(u\right)}$) Using the log of ratios rule, we can effectively calculate logs to any base.

$\ln$ is the natural logarithm whose base is $e$ (so these are negative terms).