88. Algorithmic Complexity

Efficient Ops

In the realm of algorithmic complexity, certain operations demonstrate remarkable efficiency even as input sizes grow. Joe Zack illustrates this with a scenario where twelve operations can handle 4096 inputs, and twenty operations can manage over a million inputs, showcasing the power of linear complexity 1. Michael Outlaw adds that while some algorithms may not be perfectly linear, they can still significantly outperform quadratic complexity, especially in practical applications 2.

For example, for that 1000 input size, the n squared was 1 million seconds. This is 10,000 seconds.

--- Michael Outlaw

Such efficiency is crucial in scenarios like interviews, where demonstrating an understanding of reducing complexity from n squared to n log n can be advantageous 2.

   

O(n) Complexity

Understanding O(n) complexity is essential for evaluating algorithm performance. Joe Zack explains that O(n) operations grow linearly with input size, meaning the time taken increases proportionally as inputs increase 3. This is exemplified by tasks like summing an array or finding the smallest element, where each element must be accessed 4.

If you're looping over a collection and you're hitting every item in the collection, you're automatically O(n).

--- Joe Zack

Michael Outlaw notes that even if an algorithm only examines a portion of the input, it remains O(n) due to the constant factor being ignored in complexity calculations 4.