O(n) notation.

When writing programs, it's often useful to judge your algorithms by how many operations they will take to act on any given input. Big O notation (written as $O(n)$ and also called "Big O") can be used to convey how many operations your algorithm might take, or how much memory it might occupy. Normally, you use 'worse case' to determine this, since many algorithms number of operations and memory occupied will vary based on the input.

---

$O(1)$ - Constant Time and Space

Consider this algorithm:

int getFirstElement(int[] a)

{
    return a[0];
}

No matter what size array you pass into this function, it will just return the first element, which means it always takes the exact same amount of time to run, which makes it $O(1)$ time. It also makes no additional variables or requires any extra storage to operate which makes it $O(1)$ space.

---

$O(n)$ - Linear Time

Now consider this algorithm:

int findMax(int[] a, int length)
{
    int max = 0;
    for(int i=0; i<length; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
    }
    return max;
}

As you can see, the longer the array we put in, the longer this will take to run. So adding 1 element to the size of the array will take exactly 1 more operation. Adding 2 elements will take 2 more operations, and so on. That's linear, so this is $O(n)$ in time. The size of the input directly and proportionately correlates to how long it will take to execute. However, it still only creates one variable per call, so the additional space is still $O(1)$ since its size doesn't change based on the input, it's always constant.

---

$O(n^2)$ - Quadratic Time

Not all algorithms scale linearly. A common, but less efficient, complexity is $O(n^2)$ (quadratic time), which means the execution time grows proportional to the square of the input size, $n$. This is typically seen with nested loops that both iterate over the entire input.

For example, an algorithm to check every element against every other element:

bool hasDuplicates(int[] a, int length)
{
    // Outer loop runs 'n' times
    for(int i = 0; i < length; i++)
    {
        // Inner loop runs 'n' times for EACH outer iteration
        for(int j = 0; j < length; j++)
        {
            if (i != j && a[i] == a[j])
            {
                return true;
            }
        }
    }
    return false;
}

If the input size $n$ is 10, the operations are around $10^2=100$. If $n$ doubles to 20, the operations quadruple to around $20^2=400$.

• Time Complexity: $O(n^2)$

• Space Complexity: $O(1)$ (Only temporary variables are used).

---

Why Big O is Critical for Arduino

Understanding Big O notation isn't just theory—it's vital for programming on resource-constrained devices like the Arduino.

An Arduino Uno has extremely limited resources: only about 2 Kilobytes (KB) of SRAM (working memory) and a relatively slow processor (often 16 MHz). Inefficient code can easily crash your program or make it unresponsive.

Time Constraint

On an Arduino, an $O(n^2)$ algorithm can be a disaster. For an input of $n=100$, an $O(n^2)$ algorithm requires $10,000$ operations, which can introduce noticeable lag in a time-sensitive sketch. You should always strive for $O(1)$ or $O(n)$ time complexity to keep your sketch fast and responsive.

Space Constraint

The biggest constraint on an Arduino is often the tiny amount of SRAM. An algorithm with $O(n)$ space complexity—one that requires an amount of memory proportional to the input size—can quickly use up the available $2$KB of RAM. This can lead to stack overflow or memory corruption, causing your program to crash unpredictably.

By prioritizing algorithms that are $O(1)$ in space and as close to $O(1)$ or $O(n)$ in time as possible, you ensure your Arduino sketch is both efficient and stable within its strict hardware limits.

Happy Coding!
~Tom