def factorial(number):
"""Recursively calculate the factorial of a number."""
# The base case
if number == 1:
return 1
# The recursive bit
return number * factorial(number - 1)Algorithms
1. Big O
The mathematical explanation is given in terms of the upper bound of the growth rate of a function. Very briefly: if a function \(g(x)\) grows no faster than \(f(x)\) then \(g\) is a member of \(O(f)\). This isn’t particularly helpful for intuitive understanding though.
The fundamental question is:
If there are \(N\) data elements, how many steps will the algorithm take?
This helps us understand how the performance of the algorithm changes as the data increases.
Basically, count the number of steps the algorithm takes as a function of N (and M if it involves two arrays), then drop any constants and only keep the “worst” term since we consider the worst case scenario.
Be aware, though, that this doesn’t necessarily mean a lower complexity algorithm will always be faster in practice for every use case. Take for exmaple algorithm A, which always takes 100 steps regardless of input size so is \(O(1)\), and algorithm B which scales linearly with the input so in \(O(N)\).
If we apply these to an array with 10 elements, A will take 100 steps and B will take 10 steps. So the “worse” algorithm can perform better for small data.
When an algorithm is \(O(log(N))\), the log is implicitly \(log_2\). These come up regularly in algorithms where we divide and conquer, as in the binary search, because we half the data with each iteration. If you see an algorithm has a log term in its complexity, that’s generally a clue that there is some binary split happening somewhere.
2. Recursion
Tip
Definition: Recursion
See “Recursion”.
Recursion is when a function calls itself.
In any case where you can use a loop, you could also write it recursively. I’m not saying you should, but you can.
Every recursive function should have a base case (or multiple base cases) where it does not recurse, to prevent it from entering an infinite loop.
2.1 Reading Recursive Functions
There is a knack to reading recursive functions. Start from the base case and work backwards.
- Identify the base case and walk through it
- Identify the “second-to-last” case and walk through it
- Repeat for the next-to-last case before that and walk through it
factorial(6)7202.2. Call Stack
The computer uses a call stack to keep track of the functions to call. When we enter a new recursion, we push a function call on to the stack, and when we finish executing we pop it from the call stack.
If we don’t write appropriate base cases, the recursive function can loop infinitely, leading to stack overflow.
2.3. How Deep Does This Go?
Use recursion when the depth of the problem is unknown or arbitrary.
If we have a problem where we want to go through nested structures but we don’t know ahead of time how deep they go, we can’t solve this using regular loops but we can with recursion.
For example, if we want to traverse a directory and each of its subdirectories, and each of their subdirectories, etc.
2.4. Writing Recursive Functions
Recursive algorithms are useful for categories of problems where:
- The goal is to repeatedly execute a task
- The problem can be broken into subproblems, which are versions of the same problem but with a smaller input.
Passing Extra Parameters
If we are modifying the data structure, say an array, in place, we can pass it as an extra parameter to the recursive function so that it can be passed up and down the call stack.
This is often useful for the repeatedly execute category of problems.
Top-down Thought Process
Recursion is useful when coupled with a new, slightly unintuitive, mental model of top-down problem solving.
- Imagine the function you’re writing has already been implemented
- Identify the subproblem, often the next step along
- See what happens when you call the function on the subproblem
- Go from there until you reach a base case
This is often useful for the subproblem category of problems.
3. Dynamic Programming
The idea behind dynamic programming is similar to recursion: break the problem down into smaller subproblems. For dynamic programming problems, the subproblems are typically overlapping subproblems. We also want to remove any duplicate calls.
3.1. The Top-down DP Approach
A common problem with recursive approaches is that we end up calculating the same function multiple times in the call stack. This can lead to some horrendous complexities like \(O(N!)\) or \(O(2^N)\).
The key difference to recursion is we only solve each subproblem once and store its result. This way, we can just look it up for any other calls that require it. This storing of intermediate calculations is called memoization.
We will need to pass this memoised object as an extra parameter and modify it in place, as noted in the recusion section.
3.2. The Bottom-up DP Approach
Ditch recursion and just use a loop.
This is technically another way of “solving a problem that can be solved using recursion but without making duplciate calls” - which is what dynamic programming essentially is. In this case, we do it by removing recursion altogether.
4. Space Complexity
Often the primary focus of an algorithm is its speed, characterised by its time complexity - how many steps does the algorithm take for an input of N elements?
But another useful dimension to analyse is its space complexity - how much memory does the algorithm consume for an input of N elements?
It is important to note that space complexity generally only considers the new data that the algorithm is generating, not the original input. The extra space consumed by the new data is called auxiliary space.
(However, some textbooks do include the original data in the space complexity, so it’s important to check the convention being used.)
5. Code Optimisation Techniques
The first step towards optimising your code is understanding its current complexity.
5.1. The Best Imaginable Big O
What is the best complexity you can imagine?
Also called the best-conceivable runtime.
For example, if a problem requires processing every unit of a list, then you will have to visit all \(N\) elements, so the best you can do is probably \(O(N)\). You won’t necessarily be able to achieve this, but it gives you an indication of the potential.
- Determine your current algorithm’s Big O
- Determine the best-imaginable Big O
- If they’re different, try optimising
Another mental trick that can be helpful is to pick a really fast Big and ask yourself “If someone told me they had an algorithm to achieve this Big O, would I believe them?”
5.2. Magical Lookups
Ask yourself: “If I could magically look up a desired piece of information in \(O(1)\) time, could I make my algorithm faster?”
If so, you may be able to bring in an additional data structure to accommodate this look up. Often this is a hash table.
5.3. Recognising Patterns
Start with several smaller cases of the problem and work through the answers by hand.
Does a pattern emerge that might generalise to bigger cases?
5.4. Greedy Algorithms
A greedy algorithm, at each step, chooses what appears to be the current best option.
This local optimisation doesn’t necessarily find the global optimal solution. But it can be sueful in situations where finding the absolute best option is not necessary or practical.
5.5. Change the Data Structure
If the input data were stored as a different data structure, would it make the problem easier?
In some cases, it can be worthwhile performing a pre-compute step to convert the data structure if it then allows faster algorithms to be run.
References
- A common sense guide to data structures and algorithms, Jay Wengrow.