Show notes

## What are some properties of a good algorithm?

• Low time complexity
• Low space complexity
• Memoizability
• Immutability & purity
• Concurrent / async / parallel
• General applicability (map reduce, actor model)
• “Elegant”

## Why is it interesting to formally define complexity?

• Let you compare algorithms

## Asymptotic analysis

• Always defined in terms of the size of the input (n), which can sometimes be unobvious (eg. multiplication)
• Informally defined as:
• For f(n) starting at some constant n, you will never cross the upper/lower bound function as n trends towards infinity
• Omega(n): lower bound
• Best case: in practice rarely considered:
• It’s uncommon (eg. sorting a sorted list)
• Often isn’t interesting when we consider scaling n
• Could it represent our “real world” price?
• Theta(n): bounded by two functions
• Average case: in practice rarely considered:
• Hard to quantify unless using probabilistic or randomized algorithms
• Often the average case is very close to the worst case
• O(n): Upper bound
• Worst case: often considered
• More interesting to analyze as n gets larger
• Happens more often than we would think (Searching a list for an element that doesn’t exist)
• Keep in mind that algorithmic complexity is defined in the context of what current computers can do. If processors had a SUM or SORT instruction, we’d count things differently
• Since these are just regular functions, they exhibit cool mathematical properties too, like reflexivity and transitivity!

## How do I calculate this?

• Go through every statement of your algorithm, calculate how long that operation takes (in terms of n). Ignore all constant factors.
• Once done, add everything up to get a polynomial function. BE CAREFUL OF NESTING THINGS
• Note: This works for non-recursive algorithms. Recursive ones have their own way of calculating it and we should totally make a separate episode about it, there’s some cool shiet here!

## A different kind of complexity: Kolmogorov complexity!

• Aka. algorithmic entropy
• The length of the shortest computer program needed to produce a specific output.
• Example time!
• TIL: Calculating the lower bound for finding the algorithm to describe the kolmogorov complexity is impossible

## Gotcha

• Sometimes, comparing asymptotic growth won’t cover the whole story.
• On an infinitely large data set, a linear algorithm `(f(n) = n + p)` should always be better than a quadratic one `(g(n) = n^2 + q)`, but in medium sized data set, the quadratic algorithm could be faster.
• q could be much smaller than p