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:

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:

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 n0.

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, log8 grows slower (is faster with the same “N”) than log2

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 n1 is OK) or used as a power. In this case, 3n, and (32)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, n2 (quadratic) or n3 (cubic) are polynomial.

A function has exponential growth if its output increases exponentially. Identify when n is the exponent. 5n 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 n2 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 n2 n2 Yes Insertion
Selection sort n2 n2 n2 No Selection
Shell sort n log n Depends n43 No Insertion
Bubble sort n n2 n2 No Exchanging

Algorithms and Abstract Data Types

Red-Black Tree ADT

Optimizing quicksort i mergesort with threading