My notes on complexity analysis. Not really meant to be understood by others, but I’ll put it here anyways.

What is it?

Complexity analysis is trying to find out roughly how an algorithm scales as a function of something. This “something” can be the size of the input, the number of dimensions of the input, the number of CPUs, etc. You are not looking for an exact relationship, just whether it is linear, polynomial with what degree, square root, logarithmic, exponential, factorial, etc. You are just trying to find the “class” of function that roughly describes how the algorithm scales.

Upper bound

By “roughly” we want to find the upper bound (“worst case”). The function that we find, must always be above the actual function. We call this the big O convention. You can also define roughly as the lower bound (“best case”), where our function will always be below the actual function.

With respect to what?

You can find the function that describes how your algorithm’s number of steps scales with respect to a bunch of different things, such as input size, number of CPUs, etc. Additionally, instead of looking at how your algorithm’s number of steps scales, you can look at how your algorithm’s memory usage (“space”) scales as a function of any of these things.

Intuition behind some functions

Constant

Your output doesn’t depend on the input at all. Its just a constant.

Linear

Double your input, double your output. Kind of makes natural sense.

Polynomial

If your degree is 1, you just have a linear function.

If your degree is 2, double your input, and you $2^2$ (or quadriple) your output.

If your degree is 3, double your input, and you $2^3$ (or 8-tiple lol) your output.

If your degree is 4, double your input, and you $2^4$ (or 16-tiple lol) your output.

Notice, 1 degree higher, is twice as bad in terms of scaling! Mama mia! :O

Roots

If you have a root, like square root (aka something to the 1/2), cubic root (aka something to the 1/3).

If your root is 2, double your input, you only do $2^(1/2)$ (about 1.4 times) your output.

If your root is 3, double your input, you only do $2^(1/3)$ (about 1.2 times) your output.

Exponential

Something like $a$ to the 2 or 3 ( $a$ is called the base, 2 or 3 is called the exponent).

If your starting at 2, your output is $2^2$ , 4. If you move up to 3 (not doubling, just moving up by 1 value), your new output is $2^3$ , or 8. You doubled your output, just by moving your input 1!! Holy mother… :O

Every single time you increase your input by 1, you are doubling your output!!!!

But wait! It gets worse! This is when our exponent is 2. If our exponent is 3. Moving your input just 1 point, will tripple your output! If your exponent is 4, moving your input just 1 point, will 4x (or quadripple) your output! This is no good!

Logarithmic

The opposite (inverse) of exponential. If your base is 2, You must double your input, just to move your output by 1! How amazing!

If your base is 10, you must 10-tiple your input, in order to move your output just by 1! Simply extraordinaaarrreey.

Factorial

This one is just really bad man. A single move in your input, and your output is multiplied by whatever your new input is! So if you move from an input of 2 to 3, your output is multiplied by 3. If you move from 100 to 101, your output is multiplied by 101! Holy son of a!!! Wow, this is messed up I tell ya.

Order of functions

Let’s arrange them from best to worst.

constant, logarithmic, root, linear, polynomial, exponential, factorial.

Now, you gotta remember that “best” and “worst” are always subjective. The order above is really, from the slowest scaling to fastest scaling. If you want to scale faster for some reason, then you would consider factorial to be the best.