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⁵, 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³, 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 ₅ 25 is 2 (log base 5 of 25 is 2)

• log ₁₀ 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⁰.

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₈ grows slower (is faster with the same “N”) than log₂

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¹ is OK) or used as a power. In this case, 3n, and (³⁄₂)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² (quadratic) or n³ (cubic) are polynomial.

A function has exponential growth if its output increases exponentially. Identify when n is the exponent. 5ⁿ 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.

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