</>EmbeddedInterview

What is Big-O notation, and why does worst case matter more in embedded systems?

EasyData Structures & Algorithms

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.