Notes / Data Structures & Algorithms
Time and memory complexity: what to work out first on a small MCU
On an MCU with 20 KB of RAM and a 72 MHz clock, work out the computation and memory before choosing an algorithm.
A PC has gigabytes of memory, so data structures can be generous. An MCU has a few KB to a few hundred KB of RAM, and a control loop must finish within a fixed period. So in embedded work, "does it finish in time even in the worst case?" matters more than "is it fast on average?".
Big O in working terms
| Notation | Meaning | Example |
|---|---|---|
| O(1) | Independent of data size | Putting into a ring buffer, a lookup table |
| O(log n) | Halves each time | Binary search in a sorted table |
| O(n) | Looks at every item | Array average, linear search |
| O(n²) | Nested loops | Bubble sort |
Memory budget
When designing, write RAM usage down as a table first. Add up communication buffers, sensor sample buffers, RTOS task stacks and log buffers; if the total is within 70% of the RAM you are fairly safe. Check actual usage in the map file the linker produces.
A feel for the numbers
A 10 kHz current control loop has a period of 100 µs. On a 72 MHz MCU, the ADC read, coordinate transforms, PI calculation and PWM update all have to finish within 7200 clocks. Inside a loop like that, a single division or a single sin() is counted as a cost.