> For the complete documentation index, see [llms.txt](https://cathyatseneca.gitbook.io/data-structures-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cathyatseneca.gitbook.io/data-structures-and-algorithms/appendix-mathematics-review.md). # Appendix: Mathematics Review A certain familiarity with certain mathematical concepts will help you when trying to analyze algorithms. This section is meant as a review for some commonly used mathematical concepts, notation, and methodology ## Mathematical Notations and Shorthands ### Shorthands | shorthand | meaning | | | | --------------------- | ------------------------------------------------------------------------------------------------ | -- | ----------------------- | | iff | if and only if | | | | $$\therefore$$ | therefore | | | | $$\approx$$ | approximately | | | | $$ab$$ | $$a$$ \* $$b$$ | | | | $$a(b)$$ | $$a$$ \* $$b$$ | | | | $$ | a | $$ | absolute value of $$a$$ | | $$\lceil{a}\rceil$$ | ceiling, round $$a$$ up to next biggest whole number. Example: $$\lceil{2.3}\rceil = 3$$ | | | | $$\lfloor{a}\rfloor$$ | floor, round $$a$$ down to the next smallest whole number. Example: $$\lfloor{2.9}\rfloor = 2$$ | | | ### Variables In math, like programming, we use variables. Variables can take on some numeric value and we use it as a short hand in a mathematical expression. Before using a variable, you should define what it means (like declaring a variable in a program) For example: "Let n represent the size of an array" This means that the variable n is a shorthand for the size of an array in later statements. ### Functions Similar to functions in programming, mathematics have a notation for functions. Mathematically speaking, a function has a single result for a given set of arguments. When writing out mathematical proof, we need to use the language of math which has its own syntax As a function works with some argument, we first define what the arguments mean then what the function represents. #### For example: Let $$n$$ represent the size of the array (n is the name of the argument) Let $$T(n)$$ represent the number of operations needed to sort the array We pronounce $$T(n)$$ as "T at n". Later we will assoicate $$T(n)$$ with a mathematical expression that we can use to make some calculation. The expression will be a mathematical statement that can be used to calculate the number of operations needed to sort the array. If we supply the number 5, then $$T(5)$$ would be the number of operations needed to sort an array of size 5 #### Summary $$T(n)$$ - read it as T at n, we call the function T. $$T(n) = {n^2} + n + 2$$ means that $$T(n)$$ is the same as the mathematical expression $${n^2} + n + 2$$ n can take on any value (unless there are stated limitations) and result of a function given a specific value is calculated simply by replacing n with the value $$T(5) = {5^2} + 5 + 2 = 32$$ ( we pronounce $$T(5)$$ as "T at 5") Note that when we talk about big-O notation (and related little-o, theta and omega notation) those are not functions (though it kind of looks like it) ### Sigma Notation Sigma notation is a shorthand for showing a sum. It is similar in nature to a for loop in programming. #### General summation notation. $$\sum\limits\_{i=1}^{n} t\_i = t\_1 + t\_2+ ... + t\_n$$ The above notation means that there are n terms and the summation notation adds each of them together. Typically the terms $$t\_i$$ is some sort of mathetmatical expression in terms of i (think of it as a calculation you make with the loop counter). the i is replaced with every value from the initial value of i (at the bottom of the $$\sum$$) going up by 1 to n (the value at the top of the $$\sum$$) #### Example: $$\sum\limits\_{i=1}^{5} i = 1 + 2 + 3 + 4 + 5$$ ## Mathematical Definitions and Identities Mathematical identities are expressions that are equivalent to each other. Thus, if you have a particular term, you can replace it with its mathematical identity. ### Exponents **definition** $${x^n}$$ means $$(x)(x)(x)...(x)$$ ($$n$$ $$x$$'s multiplied together) **identities** $${x^ax^b}={x^{a+b}}$$
$$\frac{x^a}{x^b} = {x^{a-b}}$$
$${({x^a})^b} = {x^{ab}}$$
$${x^a}+{x^a} = 2{x^a} \neq {x^{2a}}$$
$${2^a}+{2^a} = 2({2^a}) = {2^{a+1}}$$
### Logarithms In computer text books, unless otherwise stated $$log$$ means $$log\_2$$ as opposed to $$log\_{10}$$ like math text books **definition** $${b^n} = a$$ *iff* $$log\_ba = n$$ In otherwords $$log\_ba$$ is the exponent you need to raise b by in order to get a. **identities** $$\log\_ba = \frac{\log\_ca}{\log\_cb}$$, where $$c > 0$$
$$\log {ab} = \log a + \log b$$
$$\log (\frac{a}{b}) = \log a - \log b$$
$$\log {a^b} = {b}{\log a}$$
$$\log x < x$$ for all $$x > 0$$ $$\log 1 = 0$$ $$\log 2 = 1$$ ### Series A series is the sum of a sequence of values. We usually express this using sigma notation (see above). #### identities $$\sum\limits\_{i=0}^{n} c(f(i)) = c \sum\limits\_{i=0}^{n}f(i)$$, where $$c$$ is a constant $$\sum\limits\_{i=0}^{n} {2^i} = {2^{n+1}} - 1$$
$$\sum\limits\_{i=0}^{n} {a^i} = \frac{a^{n+1}- 1}{ a - 1}$$
$$\sum\limits\_{i=0}^{n} {a^i} \leq \frac{1}{a-1}$$ if $$0 < a < 1$$
$$\sum\limits\_{i=1}^{n} {i} = \frac{n(n+1)}{2}$$
$$\sum\limits\_{i=1}^{n}{i^2} = \frac{n(n+1)(2n+1)}{6}$$
$$\sum\limits\_{i=1}^{n}{f(n)} = nf(n)$$
$$\sum\limits\_{i=n\_0}^{n} f(i) = \sum\limits\_{i=1}^{n} f(i) - \sum\limits\_{i=1}^{n\_0 - 1} f(i)$$