How Algorithm Efficiency Is Measured
Big O Notation for Beginners
Back to the Basics
Put simply, algorithms are a way of solving a class of problems. They are a ‘finite sequence’ made to work with any programming language. Think of these as instructions, just like a recipe! It includes step-by-step directions that can be applied to return the desired result. Since all programming languages, share some commonalities such as loops and conditional statements, we can apply these to any programming language.
Working is Not Good Enough
It’s not okay to assume that your algorithm is acceptable, just because it’s working. That’s only one part of the problem-solving process. It’s best practice for programmers to refactor their work. We must question the efficiency of our methods. Remember, there is more than one route we can take to get to our final destination.
Units of Measurement
We can grade our program’s efficiency based on total complexity, which is made up of approximate time and space measurements. This concept is referred to as Big O Notation. If you’re unfamiliar with this idea, stick with me here. We’re not building a flux capacitor here! I’m going to introduce you to how Big O Notation is formalized.
Time Complexity
Time complexity represents the time required by the algorithm to run to completion. Many algorithms are so fast that we can’t use a timer for accurate results, even if we use the same machine for counting time.
Instead, we can use this formula below to determine time complexity.
T(n) = c * n
N represents the input we are working with and C represents time taken.
Scaling from Best to Worst
The result of time complexity is generally defined as constant, logarithmic, linear, N-log-N, quadratic, cubic, or exponential. As you can see in the chart below, measurement is given as O(n). N still representing the input that we are working with. These are listed in order of efficiency. Constant time is ideal because it takes the same number of operations no matter what N is. Exponential time is practically our worst nightmare, because it grows very quickly and will cause our program to respond at a snail’s pace.
Things to Keep in Mind
Integers and small terms don’t get counted when calculating complexity. Arithmetic operations, variable assignments and accessing elements in an array are also considered constants and do not change the result. When you’re working with a block of code that contains a loop, the complexity is measure for the length of the loop. If there is another loop inside that loop, it’s considered quadratic.
Space Complexity
Space complexity is the total amount of memory used by a program, including the space of input values during execution. In order to figure out the space complexity, we can calculate the space occupied by the variables used in an algorithm. A program with terrible time efficiency will run much slower than we want, but a program with terrible space efficiency might not run at all. The question to ask when determining space complexity is, does this variable scale with the size of our input? (Typically, integers don’t matter here as they take up the same amount of space.) The ideal space complexity is also constant which means the space taken does not change with the input given.
Conclusion
Learning Big O Notation takes time and practice. However, this is a smart investment as it helps us to understand what makes a great program. We can recognize where we have room for growth and work towards it. Being able to create effective algorithms flexes our problem-solving muscles. It gives us a way to grade our work and revisit the drawing board to make it even better than before. I hope that this has sparked your curiosity to dive deeper into this topic. Check out the resources below for more on calculating complexities.
Resources
https://www.faceprep.in/data-structures/space-complexity/
https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/
