Computational complexity

Computational complexity refers to the amount of time and resources (memory space) required
by a computer algorithm to solve a problem.

It's important to understand that some problems are inherently more difficult to solve than
others, and as a result, require more time and resources. The lower the requirements, the better.

An algorithm is a set of instructions for solving a problem or completing a task, but we’ll dive
deeper into algorithms later. What's important to know about algorithms, is that developers
write them everyday.

In fact, every function, no matter how simple or complex can be considered an algorithm.

As developers, we have to learn to write code that is as fast and efficient as possible, and
knowing computational complexity will drastically help us understand how performant our code
is, and recognize the different places where it can be improved.

Speaking of which...

Big O notation

Big O notation is what we use to describe how much time an algorithm takes to run or how
much space (memory) the algorithm requires.

It expresses the upper bound of the growth rate of an algorithm's running time or space
usage.

The performance is also relative to the size of the input passed into the algorithm. Typically, the
larger the input, the more time and resources the algorithm takes.

It’s important to note here that the units for time and space are not tangible measurements.
This means that we’re not measuring the time in milliseconds, seconds, minutes, etc, or the
space in bytes, kilobytes or megabytes. Instead, it measures the rate of increase in resource
consumption (time or space) relative to the size of the input.

Also, we use the term operations to denote the units of time or memory consumed.

Still with me so far? Here's where it gets a little more difficult to understand, but stick with it.

My fellow ZTM instructor (who has an incredible data structures and algorithms course) also put
out a free Big O tutorial that you can check out but I'll also walk you through some of the key
concepts below.

Big O complexity always comes in the form of O followed by brackets that contain the category
of complexity, such as O(1), O(log n) or O(n log n).
Let’s take a look at the following chart to understand how these categories compare against
each other:

Here, we can see that the larger the input (i.e. more Elements on the x-axis) the more resources
the algorithm consumes (i.e. the number of operations on the y-axis).

Each line represents a different category of performance, and the order of these categories
from best to worst is:

1. O(1)

2. O(log n)

3. O(n)

4. O(n log n)

5. O(n2)

6. O(2n)

7. O(n!)

Let’s quickly run through what each category means first, then later when we talk about
algorithms we’ll learn about how to determine what category an algorithm will fall into.

I’m going to talk about them from the perspective of time but the same explanation can apply
for memory.

1) O(1) - Constant complexity

Constant time is the best category to have. This means that regardless of the input size (n),
whether it’s zero elements, one element or one billion elements, the algorithm will take the
same amount of time to run.

2) O(log n) - Logarithmic complexity

Logarithmic time is the next best time to have because it means the time taken barely increases
while the input increases.

In Big O, whenever we see log we mean log base 2 or log2 meaning O(log n) is actually O(log2n).

If you’re unfamiliar with logarithms, logarithms help us solve the inverse of exponents.

The logarithm of a number (n) is the exponent to which the base number (2), must be raised to
produce it (n). So 24 = 16, this means that log216 = 4.
We’ll see a real life example in an algorithm called binary search later when we look at
algorithms.

Looking at three input sizes of 16, 1000, and 10000000, we see:

log2 16 = 4

log2 1000 = 9.96

log2 10000000 = 23.25

Even though our number of operations grows with the increasing inputs, it’s still significantly
lower than the size of the input.

The input grows from 1000 to 10,000,000 but our operations consumption only grows from 9.96
to 23.25.

3) O(n) - Linear complexity

Linear time means that the amount of resources consumed by the algorithm grows at the same
rate that the input grows (for simplicity sake 1:1).

If the input is 1 element, it takes 1 operation; if the input is 100 elements, it takes 100
operations; if the input is 1000000 elements, it takes 1000000 operations.

While this sounds bad, it’s actually still pretty good as our line O(n) is still in the green zone in
the chart above. This is because the next categories are significantly worse in their growth.

4) O(n log n) - Loglinear complexity

Loglinear time is worse than linear time, and it’s a combination of linear and logarithmic.

It's commonly seen in recursive sorting algorithms and binary tree sorting algorithms. What it
means is that for each element in the input (n), will take log2n time to run, hence n times log2n.

5) O(n2) - Quadratic complexity

Quadratic time is now very inefficient, and while some algorithms can only be written in this
complexity category, this and each subsequent category should be a warning sign you need to
optimize and refactor your solution.

Quadratic time represents a growth rate where the operations taken is the square of the size of
the input.

This means an input of 2 elements has 4 operations; an input of 10 elements has 100
operations; and an input of 10000 elements has 100,000,000 operations.

This means that each element in the input (n) requires n operations to run.
6) O(2n) - Exponential complexity

Exponential Time is another extremely inefficient complexity category.

This means that the number of operations taken is exponentially growing relative to the size of
the input.

This is even worse than quadratic time since quadratic time has the base as the input size (n),
whereas in exponential time you are looking at an exponent equal to the input size (n).

We can see this by comparing quadratic and exponential times with an input size of 20:

202 = 400

220 = 1,048,576

7) O(n!) - Factorial complexity

Factorial complexity is the worst possible complexity.

It is an incredibly rare complexity to encounter, largely seen only in security related

Factorial is a mathematical equation often used to calculate the number of possible

9 Factorial (or 9!) can also be calculated as:

9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880.

Compare this against quadratic and exponential complexity above with an input size of 20:

20! = 2.432902e+18 operations

Or it can also be written as, 2.432902 * 1018 operations.

tl;dr

We want to run fast algorithms, and so the first five categories are the main ones you’ll see:

1. O(1)

2. O(log2$ n)

3. O(n)

4. O(n log2 n)

5. O(n2)
Don't worry because this will all make more sense as we continue to work through this guide.

In order to better understand these categories, we’ll have to learn about data structures and
algorithms to see them applied, so let’s dive in while using the above list and chart as a
reference.