N-notation
Episode #2 of the course Kurt Anderson by Computer science fundamentals
Welcome back!
Yesterday, we covered the basics of how computers themselves work. Today, we will learn the building blocks to algorithm analysis, a core concept of computer science.
What Is N-notation?
N-notation is a way of representing the run time of an algorithm so it can be compared to another algorithm. N-notation is NOT an analysis of how long an algorithm will take to run, but an analysis of how the algorithm will scale with more and more input data.
This method is based off looking at the input of the algorithm and analyzing how the algorithm works with this input. However, we don’t particularly know how many pieces of data will come in at any given moment. What we do is replace this input number with a variable, n.
For example, let’s say that we have an algorithm that runs through the amount of Facebook friends you have. When we are writing the algorithm, we have no clue how many friends are going to be added as input. You could have 25 or 2,000 or two. So, instead of giving an actual number, we just say n pieces of data will be put into this algorithm.
How to Use N-notation
How do we use this to compare two algorithms? What we do is look for significant differences in the algorithms. Given the input of n, how does the program react?
From the chart above, we can see these different relationships graphed out. The x-axis (bottom of the graph) shows how many pieces of data come into the algorithm. The y-axis (left side) shows how many operations the program will have to do given the number of pieces of data.
What is this chart displaying, then? It’s displaying the relationship we were talking about. The center green line is n. This means that if we insert n pieces of data, the algorithm will take n number of operations. One hundred pieces of data will take 100 operations, 200 will take 200, and so on. Notice how some other lines require substantially more operations given the same amount of input.
A real-world example of this might be copying a handwritten spreadsheet into Excel. You, in this instance, are the algorithm. For every piece of data on that hard copy, you will have to make one operation, inserting it in to Excel. If there are 100 pieces of data, it will take you 100 insertion operations. Whatever the input size is, you will have to do that many operations. This makes the run time for this, n.
Let’s say instead we are tasked with checking the spreadsheet and seeing if any value is the same as any other value. This is a substantially more tedious process. We must take each piece of data and compare it with every other piece of data. In this case, we will have n for every piece of data and then an additional n for comparing that with every other piece of data. This results in n*n, or for every piece of data, we will have to check every other piece of data. We can simplify this to n^2 (i.e., n*n).
The key part here is to recognize the difficulty of the problems as they scale. The first problem is pretty easy. You could have 1,000 pages or 100,000 pages, and the problem wouldn’t get out of hand. It could get boring, but nothing a number of hours couldn’t solve.
With the comparisons, however, imagine checking the full 1,000 pages for every single number. What if you have 10,000 or 100,000 pages? The problem quickly becomes unmanageable. This is what we are looking at with n-notation—this relationship between input and growth of the problem.
Here is a comparison of how the different algorithms might work with actual numbers.
Key takeaways:
• N-notation is used to compare the growth of algorithms, not their actual time.
• N is used as the variable for how many pieces of data the algorithm inputs. We then look at the relationship with how many operations it must do given this amount of input.
Tomorrow, we will extend on this idea with Big O notation.
Cheers,
Kurt
Recommended book
Share with friends