Photo by Blake Connally on Unsplash Blake Connally Unsplash Your algorithm could be slow and you may not even notice it unless you learn this essential skill. Many programmers create algorithms that turn out to be slow, but they have no idea it’s slow. We need a way to measure how long an algorithm takes to run. How do we measure how long an algorithm takes to run? We could run an algorithm 10,000 times and measure the average time taken but this creates a problem. Say we have an algorithm that takes a shopping list and prints out every item on the shopping list. If the shopping list has 3 items at most the algorithm could take 3 seconds to run. If the shopping list has 10 items it may take 10 seconds to run. A problem is fabricated here. How do we know what the “perfect” input size is to get the “perfect” measure of how long the algorithm takes? For this reason we use a notation called Big-O (pronounced Big Oh) notation. Big 0 notation is a notation used to describe how efficient an algorithm is. Big-O is easy to read once you know this table: Where the further right they are, the longer it takes. Big O notation uses these functions to describe algorithm efficiency. Taking our shopping list as an example then the algorithm will be O(n). We don’t know how many items are in the shopping list so we give it an alegrabic varaible such as n. We then print each item to the screen which takes o(n) time. Let’s run through every single one of these. Constant An constant algorithm is an algorithm that doesn’t take more time if the input size gets larger. Let’s look at a quick example: So the numbers here are small but: Takes roughly the same amount of time. But what if the numbers were extra large like… The numbers are hardcoded in. If you input 50, it will still add these two numbers together. Because of this it doesn’t take more time to add them together depending on the input size. They do not scale with input size. They are a constant. Log n You might be wondering “what is log n”? Well… A logarithm is sometimes called a log. Frequently in base 2 binary but can differ). Let’s do a quick example: In this example what is being asked is “3 to what power gives you 9”. So this is 3 to the power of 2 gives us 9, so the whole expression looks like: A logarithmic algorithm “halves” the list every time it’s run. It’s what Binary search is (which is explained later). If you give the algorithm a list of 10 items like so: a = [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10] a = [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10] And the algorithm halves it every time like so: a = [1, 2, 3, 4, 5] a = [1, 2, 3]a = [2] a = [1, 2, 3, 4, 5] a = [1, 2, 3]a = [2] Then it is a logarithmic function. Polynomial time If we have our shopping list from earlier and it looks like this: a = ['water', 'vegetables', 'Bose QC35'] a = ['water', 'vegetables', 'Bose QC35'] If you went through every item in the list and said it out loud then the complexity will be n. This is because there are n items in the list and the number of items can increase or decrease. For it doubles the time of the input. An example of this is: a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]for i in a: for x in a: print("x") a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]for i in a: for x in a: print("x") If you see a nested for loop like above then it’s n², if it’s 3 nested for loops then it’s n³ and so on. Exponential This type of algorithm is the slowest of them all. An example of this is say you have a password consisting only of numbers (so that’s 10 numbers, 0 through to 9). You want to crack a password which has a length of n, so to bruteforce through every combination you’ll have: Combinations to work through. In Big O notation, we always use the worst case scenario for our calculations. Computer scientist are pessemistic. worst case Simplifying Big O notation What if your algorithm looks something like O(n + n²)? Well, there are some super useful rules to simplify your algorithm. Drop the constants If you have an algorithm described as O(2n), drop the 2 so it’s O(n). Drop the non-dominant terms O(n² + n) becomes O(n²). Only keep the larger one in Big O. If you have a special sum such as O(b² + a) you can’t drop either because without knowledge of what b and a are. Summary Bet you were expecting some hard to understand guide to Big O huh? Well, this is all it is. You need to memorise (or learn) the hierarchy, take some algorithms and find out what their Big O notation is. Big O represents how long an algorithm takes but sometimes we care about how much memory (space complexity) an algorithm takes too. There are other forms of measuring algorithm time complexity such as Big Theta which is the least amount of time an algorithm takes. Stick around for the next article which will be about search algorithms and how to find a book in a bookstore! If you liked this article, connect with me! LinkedIn | Twitter | Website | Newsletter LinkedIn Twitter Website Newsletter
