Introduction to Algorithm Complexity

Math for CS · Axiom Academy

INTRO Introduction to Algorithm Complexity Why measuring efficiency matters and how we do it Imagine you have two sorting algorithms. Both produce the correct output. But Algorithm A takes 1 second on a million items, while Algorithm B takes 3 hours. The difference is algorithmic complexity . Algorithm complexity measures how an algorithm's resource usage (time or space) grows as the input size increases. It answers: "How does this algorithm scale?" In the real world, inputs grow. Databases get bigger. User bases expand. An algorithm that works fine on 100 items might be catastrophically slow on 10 million. Complexity analysis tells us which algorithms will survive that growth. Key insight: We don't measure wall-clock time (that depends on hardware). Instead, we count fundamental operations as a function of input size . Time Complexity vs Space Complexity Algorithms consume two resources: Time complexity: How many operations does the algorithm perform as a function of input size ? Space complexity: How much memory does the algorithm use as a function of ? Example: Linear search through an array of elements checks each element one by one. Time: up to comparisons in the worst case Space: extra memory (just a loop variable) Both matter, but time complexity is usually the primary concern. An algorithm that runs in reasonable time but uses a lot of memory can often be improved with clever data structures. An algorithm that takes exponential time is hopeless regardless of memory.

This is the written version of the interactive lesson above. See the full Math for CS course.