A Symptomatic Flotation
At this point we’ve been talking about different algorithms and data structures for what feels like weeks. Perhaps months. Instead of breaking down another data structure this week I’d like to talk about how these data structure and algorithms are graded. The system of ranking the good ole Ds and As is known as Asymptotic Notation. Asymptotic notation measures what is known as the runtime of an algorithm. This is important because when algorithms can deal with massive amounts of data, and what may seem like a small amount of runtime difference on a small scale can grow to be quite large as the inputs for the algorithm increase in value. Asymptotic notation is usually expressed using variables; most of the time the letter N, and a big O. Like this.
O(n)There are actually three different ways to notate the runtime of an algorithm. Omega, O, and Theta. O notation, or big O as it is known is the most common because it measures the worst possible scenario based on a given input. Given that these algorithms are dealing with massive amounts of data, it’s generally considered expedient to just use big O, when talking about runtime.
Now let’s talk about the concept of infinity. Very often, when notating run time for algorithms, you won’t see any coefficients or small incidental variables. The reason for this is that, as these algorithms deal with amounts of data approaching infinity, those numbers really don’t mean anything. When saying that an algorithm will take n +6 amount amount of resolutions to resolve, the six doesn't really matter if n is a number approaching infinity. For this reason all big O notations can be broken down into a relatively small amount of very simple expressions.
When building algorithms, knowing how certain algorithmic behaviors map to different big O speed is important in making sure you are using efficient algorithms.
And that’s all there is to know about asymptotic runtime. In the next few weeks I’ll be going over some interesting algorithms that use concepts such as bubble sorting and trees. Try to contain your excitement!
