What is Big-O notation, and why does worst case matter more in embedded systems?
Short answer: Big-O describes how an algorithm's time or memory grows with input size n, ignoring constant factors: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic. Embedded and real-time code cares most about the worst case (a deadline must be met every time), about memory (often fixed at compile time), and about constant factors (n is small, so a simple O(n²) loop over 16 items can beat an O(n log n) algorithm with more overhead).
| Structure / algorithm | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Array | O(1) | O(n) (O(log n) sorted) | O(n) | O(n) | contiguous, cache friendly |
| Singly linked list | O(n) | O(n) | O(1) at head | O(1) given previous node | pointer per node |
| Ring buffer | – | – | O(1) | O(1) | fixed size, FIFO |
| Hash table | – | O(1) avg, O(n) worst | O(1) avg | O(1) avg | needs a good hash, load factor |
| Balanced BST (red-black) | – | O(log n) | O(log n) | O(log n) | ordered traversal |
| Binary heap | O(1) min | O(n) | O(log n) | O(log n) min | priority queues, timers |
| Bitmap | O(1) | O(n/word) with CLZ/CTZ | O(1) | O(1) | allocation, priority sets |
| Sort | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|
| Insertion | O(n²) | O(n²) | O(1) | yes |
| Merge | O(n log n) | O(n log n) | O(n) | yes |
| Quick | O(n log n) | O(n²) | O(log n) stack | no |
| Heap | O(n log n) | O(n log n) | O(1) | no |
| Counting/radix | O(n + k) | O(n + k) | O(k) | yes |
Interview tip: when you give a solution, state time and space complexity and the worst case unprompted, and mention whether it allocates memory or recurses.