Recall, our concern when selecting among different possible algorithms is ultimately about how those algorithms will scale (“What happens when this same little function is passed a truly massive hash of user data?”) An algorithm that works well-enough on our local machine executing our little test cases might stumble when deployed at scale, so our Big Question is, How resource hungry are our algorithms as inputs get larger? How much longer does it take and how much more memory does it require when the input size goes up by 1? When it doubles? When it increases by an order of magnitude? 

What we want is, essentially, a rate of change. Or really, two rates of change: the rate of change for time taken – the time complexity of our algorithm – and the rate of change for memory space needed – the space complexity of our algorithm. These rates of change are often represented using what’s known as ‘Big O Notation’ – with the “O” standing for Order of Magnitude. 

There are two notable characteristics of this notation system. First (and as that name suggests) Big O Notation is a coarse-grained metric focused on capturing just the big rate-of-change trends. If, for instance, an algorithm has two components that increase linearly with the input and one component that increases quadratically, Big O Notation will ignore the linear terms entirely and focus just on the dominant growth trend: the quadratic growth.

The second important feature of Big O Notation is that it is used to characterize the worst case scenario for the time and space complexity of an algorithm – i.e. the upper limit on resources, assuming the algorithm is forced to take the maximum possible amount of time/space.

There’s good reason for that, for not focusing on average case scenarios or, especially, best case scenarios. Suppose we have an algorithm that iterates through an array to check whether it includes a particular value. In the best case scenario, the element is first in the array, so we’d expect our algorithm to have constant time complexity: our loop always cuts off after the first iteration, no matter the input size. But obviously that tells us nothing about how our algorithm will actually perform at scale! That’s a worthless metric. On the other hand, the average case scenario is a much more meaningful metric. We really do care how our algorithm with perform on average. But we won’t always have a good sense for what “the average case” looks like. That will be highly context dependent – indeed, if there’s a fact of the matter at all, said fact often won’t be knowable.

That’s why it makes most sense to focus on the time/space complexity of the worst case scenario: those values really do tell us something helpful about our algorithm, and they don’t require extra knowledge about the particular circumstances in which the algorithm will be used in the real world.


Big O Notation: the categories
Our goal is to select algorithms whose time / space needs grow more slowly as input sizes get larger. Which is to say, slower growth is strictly better. Accordingly we need, first, to be able to identify the time/space complexity of a given algorithm, and we need, second, to know which complexity categories indicate slower rates of time / space growth. 

So, here’s a list of the most common time / space complexities, rendered in Big O Notation and in order of increasing complexity. Each particular algorithm will one complexity value for its time growth and another value for its space growth. (i.e. the time complexity and space complexity are separate properties that can, but don’t have to be, different.)
O(1) (“oh of one”) – constant complexity. The procedure takes the same amount of time/space, regardless of input size.
O(logN) (“oh of log en”) – logarithmic complexity. Each additional doubling of the input size increases time/space complexity by the same fixed amount. 
O(N) – linear complexity. Time / space needs increase at the same rate as the input – e.g. doubling the input size doubles the amount of time needed.
O(NlogN) – linearithmic complexity. Time/space needs increase at a rate intermediate between N growth and N*N (i.e. N^2) growth as inputs increase. (The second term, logN, grows much slower than a second N would but still gradually increases the slope, causing an upward curve.)
O(N^2) – quadratic complexity. Doubling the input size increases the time/space complexity by a factor of 4.
O(N^3) – cubic complexity. Doubling the input size increase time/space complexity by a factor of 8.
O(2^N) – exponential complexity. Each additional element added to the input doubles the amount of time/space required.
O(N!) – factorial complexity. Each additional element N-ples the amount of time/space required (e.g. the 3rd element triples it, the 4th element quadruples it…)

In general, when selecting an algorithm from a list of possible approaches, we’ll want whichever one has the lowest complexity, given the above ordering. (e.g. some problems can be solved with either a binary search or a pointer strategy, but since binary searches have time complexity O(logN) and pointer strategies tend to have complexity O(N), we should go with the binary search.)

It’s more complicated than that, of course. Not least because we care about time and space complexity, and there are often trade-offs between the two – i.e. an algorithm with excellent time complexity may have larger memory demands and vice versa. Time complexity will tend to dominate in importance, though, so it’s usually best to focus on that.

Evaluating an algorithm’s time complexity
The time complexity of an algorithm as a whole is, roughly, equal to the time complexity of its most time-complex component. (Though, it’s non-trivial to articulate how we should go about individuating an algorithm’s components! A for loop is a component… unless it’s nested inside another for loop, in which case it’s part of the outer loop component.) Each computational step – from initializing a variable, to adding two integers, to iterating through a collection – has its own time / space complexity, and getting good at assessing algorithmic complexity means getting good at assessing the time / space requirements for different computational steps (and, again, at being able to individuate an algorithm into separable components.)

“Assessing” the complexity of a given step will often requires brute force memorization. For instance, we may need to memorize the fact that JS’s Array.prototype.findIndex() has O(N) time complexity while Set.prototype.has() has O(1) complexity – which difference arises out of particular details that we probably won’t be able to intuitively infer about how arrays and sets are implemented in JavaScript. Othertimes, we may be able to intuit complexity facts using our basic knowledge of how data structures work. (For instance, we can infer that pop() and push() have time complexity O(1) while shift() and unshift() have time complexity O(N) b/c we know that shifting operations create a need to move every element in the collection up/down an index while push/pop operations don’t.)

Here’s an incomplete list of time complexities for common operations / algorithms – though, keep in mind that expressions themselves can be arbitrarily complex and so saying “logical expressions are evaluated in constant time” is true only insofar as the expression doesn’t itself have sub-components with higher time complexities (e.g. an O(N^2) function call).
O(1)
Logical expression evaluation 
Mathematical operations
Conditional flow statement evaluation
Return statement evaluation
Variable / property declaration and reassignment
Property access / indexical lookup / has() methods
Primitive value creation / value coercion
Push / pop operations
for loops that iterate through a static collection of values whose size does not depend on the size of the input (e.g. iterating through the alphabet)
O(logN)
Binary search operations
for loops where the loop counter is doubled or halved on each iteration
O(N)
List abstraction methods (w/ potentially higher complexities depending on the details of the callback function)  – forEach, reduce, map, filter, some
for loops that iterate through the input (but not if they iterate through a fixed range of nums)
Array/object/collection methods that may need to shift, manipulate, copy, or search all elements – shift, unshift, concat, indexOf, slice, splice, fill, values, keys, entries, assign, reverse, includes, match, replace, search, split, etc.
O(NlogN)
Quick sort / merge sort algorithms (including Array.prototype.sort())
Any process that does a binary search on each element of a N-sized collection
O(N^2)
Two nested iterations – a for loop inside a for loop, a map inside a filter, etc.
Bubble sort / selection sort / insertion sort algorithms
O(N^M)
M nested iterations
O(2^N)
Recursion without memoization, when each recursive call may necessitate 2+ more recursive calls (e.g. calculating Fibonacci numbers)
O(N!)
Search-all-permutations problems

Again, an algorithm as a whole is generally said to have the time complexity of its most complex component. If an algorithm has one step with constant time complexity O(1), another with linear time complexity O(N), and a third with quadratic time complexity O(N^2), we don’t say that it has time complexity of O(N^2) + O(N) + O(1); we say it has time complexity of O(N^2). After all, Big O Notation is a coarse-grained measure focused on just the largest contributors to performance, and we know that as input sizes trend toward infinity, the contribution of smaller-complexity components will become negligible.

Relatedly, if an algorithm consists of just three separate mapping steps, we might be inclined to say that it has time complexity O(N) + O(N) + O(N) – or O(3N). But since the constant is ultimately a negligible contributor to the time complexity trend, we omit the 3 and simply say that the algorithm has complexity O(N).

That said, there’s an important exception to this involving algorithms with multiple inputs. If our algorithm does two mapping steps on one input collection (N) and a filter step on a different input collection (M), we’d say it has complexity O(N) + O(M), thereby signaling that the execution time grows linearly with the size of both inputs. (Notice: it’s not O(N + M) but O(N) + O(M).)

Space Complexity
Assessing space complexity is generally less important and, often, less complicated. 

Strictly speaking, what we care about is not all the space used in executing a function but specifically the additional space used – called the ‘auxiliary space complexity’. We don’t care about the space required by the input only about the space needed for managing our task on the input. (Trivially, the space needed to hold the input increases linearly with the size of the input. We don’t need Big O notation to keep track of that fact.) What matters is the amount of extra space we need to set aside for each additional element in the input.

Creating primitive values basically always has a constant space complexity. Thus, the primary thing to pay attention to is the creation of new collections and specifically those that depend on the input in some way (whereas, e.g., a basic object mapping digits to their integer counterparts has a constant space complexity.) 
Anytime we apply a mapping function to our input, we need to set aside space for a collection the same size – which means mapping steps have space complexity of O(N). If we create a 2-D array from our input where each element of the new collection is the same size as the input collection, we will have a space complexity of O(N^2). This is why algorithms that iterate through collections without mapping or filtering them – using, e.g., counters, pointers, constants OR doing in-place swaps rather than copy / modify steps – tend to have lower space complexity.

Accordingly, reducing space complexity usually means reducing our use of auxiliary collections and, where possible, reducing the dimensions of the ones we do end up needing.

One aspect of space complexity that can take a little getting used to is that creating variables and primitive values really does have no effect on the space complexity of our algorithm. An algorithm could include thousands of pointers and constants and so long as none of them adjust with the size of the input, the algorithm would still count as have a space complexity of O(1).
