Complexity basics

 From the earliest days of computing, a central question has been how we can solve a problem as efficiently as possible. That has meant several things over time to different people, but in modern times, we’ve settled on efficiency over two different parameters (which generally require tradeoffs with each other): the number of steps something takes, and the amount of memory it takes to do it.

 In computer science, we group things into complexity classes based on the worst-growing term, ignoring any coefficients. Think about it for a second, and pull up Desmos or another graphing calculator to follow along:

• A^2+3A-25: it looks like A^2, because eventually, the A^2 term will be so much bigge than 3A or 25 that A^2 will dominate
• X^3+2^X-1000000: it looks like 2^X because, eventually 2^X will be much bigger than X^3 or 1000000
• x!-10^x-x^100-1000000000: it looks like x! because, eventually, x! will dominate all of 10^x, x^100, and 1000000000

In general, we prefer functions at the top of this list more than at the bottom, in terms of describing both space and time:

• constant is better than
• logarithmic is better than
• linear is better than
• log-linear is better than
• polynomial is better than
• exponential is better than
• factorial is as bad as it gets

Let’s look at each one, with an example of each

• “Go to this place in memory” is constant
• “Do binary search through an already-sorted array” is logarithmic
• “Do linear search” is linear
• “Do merge-sort” is log-linear
• “Do traditional, grade-school, digit-by-digit multiplication” is polynomial
• “Count the number of nodes in a binary tree of a certain height” is exponential
• “Tell me all the ways I can form a line out of students in my class” is factorial

Another way of looking at things:

• If a problem always requires the same number of steps, it is constant
• If there’s a single loop in the code, that moves by i++ or i--, it’s linear
• If there's a single loop in the code, that moves by i*=2 (or i/=2) or something similar, it's logarithmic
• If your problem splits things in half recursively and brings them back together at the end like MergeSort, it's log-linear
• If there are some number of nested loops: i inside j inside k…, then it’s polynomial, and the degree is the depth of the nesting: i inside j inside k is 3 deep, so this is n^3
• If one problem causes there to be some number of problems, which creates that many sub-sub problems for each sub problem, and so on (1 problem becomes 2 becomes 4 becomes 8…), then it’s exponential by the rate at which the problems are multiplying: 1 problem into 3 into 9 into 27 is 3^n, but 1 problem into 2 into 4 into 8 into 16 is 2^n, but either way 2^n or 3^n are both exponential
• If you have no other choice but to calculate every possible arrangement of something, in order to get to a solution, then you’re looking at n! (like, for example, the hilariously bad “bogosort”: randomize a list, check if it’s sorted; if not, randomize again; keep randomizing and checking until a shuffle results in a sorted list)