# Algorithms

#### Exponents vs. Logarithms

An exponent is just a way to show repeated multiplication. For instance, in 32 = 3*3 = 9, the 3 is called the base of the exponent and the superscripted 2 is called the exponent or power. An exponential function tells us how many times to multiply the base by itself. Here are some examples:

For 2

^{5}, we take the 2 and multiply it by itself five times, like this: 2*2*2*2*2 = 4*2*2*2 = 8*2*2 = 16*2 = 32. This yields a result of 32.For 10

^{3}, we multiply 10 by itself 3 times, yielding a result of 1000.

A logarithmic or log function is the inverse of an exponential function. We can use a log function to find an exponent. Continuing with the above examples:

log

_{5}25 is 2 (log base 5 of 25 is 2)log

_{10}1000 is 3 (log base 10 of 1000 is 3)

#### Growth complexity

In computing science, the **order of growth** is to look for, as tight as possible, an upper bound of the growth as the function of the size of the input on the **worst** case.

In other words, order of growth will depend on the size of the input, always taking into account the worst scenario (not the best one or the average onne…)

We use Big O notarion to express the orders of growth

A function has **constant** growth (**O(1)**)if its output does not change based on the input, the N. The easy way to identify constant functions is find those that have no nnnn in their expression anywhere, or have n^{0}.

A function has **logarithmic** growth (**O(log n)**) if its output increases slowly with size of its input (normally is very close to constant…). The easy way to identify logarithmic functions is to find those that divide n in their expression. Inside the logarithmic class, log_{8} grows slower (is faster with the same “N”) than log_{2}

A function has **linear** growth (**O(N)**) if its output increases linearly with the size of its input. The way to identify linear functions is to find those where N is never raised to a power (although n^{1} is OK) or used as a power. In this case, 3n, and (^{3}⁄_{2})n are linear.

A function has **polynomial** growth if its output increases according to a polynomial expression. The way to identify polynomial functions is to find those where n is raised to some constant power. In this case, n^{2} (quadratic) or n^{3} (cubic) are polynomial.

A function has **exponential** growth if its output increases exponentially. Identify when n is the exponent. 5^{n} is exponential.

**Factorial** expressions grow more rapidly than exponential, and are the worst case. Factorial can be calculated for 0 < N < 30 (or 40), with dramatical growth for each N increase. From N > 40, the time is too big even for the fastest computer.

Name | Best | Average | Worst | Stable | Method |
---|---|---|---|---|---|

Quicksort | n log n | n log n | n^{2} |
In place, no | Partitioning |

Merge sort | n log n | n log n | n log n | Yes | Merging |

Heapsort | n log n | n log n | n log n | No | Selection |

Binary tree sort | n log n | n log n | n log n (balanced) | Yes | Insertion |

Insertion sort | n | n^{2} |
n^{2} |
Yes | Insertion |

Selection sort | n^{2} |
n^{2} |
n^{2} |
No | Selection |

Shell sort | n log n | Depends | n^{4⁄3} |
No | Insertion |

Bubble sort | n | n^{2} |
n^{2} |
No | Exchanging |

#### Algorithms and Abstract Data Types

Red-Black Tree ADT

https://en.m.wikipedia.org/wiki/Red%E2%80%93black_tree

Optimizing quicksort i mergesort with threading

http://pages.mtu.edu/~shene/NSF-3/e-Book/index.html