What is Big O and Why Do We Use It?
A simple explanation for Big O and the terms broken down so that they are easy for anyone to understand
What is Big O?
Big O Notation is a form of symbolism that helps us choose the right algorithms in various situations. It also helps us better understand the performance of algorithms.
What is an Algorithm?
The following definition was originally found in a FreeCodeCamp Article. In it’s most basic form, an algorithm is a set of detailed step-by-step instructions to complete a task. For example, an algorithm to make coffee in a french press would be:
- Pour water into the kettle, close the lid, and turn it on.
- Take the lid off the french press and pour in 17 grams of ground coffee.
- When the water in the kettle is boiling, pour 290 grams of hot water into the french press.
- Put the lid of the french press back on with the plunger up.
- Wait 4 minutes.
- Gently press the plunger down until it reaches the bottom.
- Pour coffee into a mug.
Algorithms can be thought of in many ways as recipes. If you were having a friend over for dinner, you’d probably want to choose the recipe that includes food they like and when it comes to choosing algorithms you’d want to use an algorithm that the problem you’re trying to solve is compatible with.
What is Notation?
Notation at it’s core is a way of using symbols as a form of communication.
Why do we Use Big O?
We use Big O Notation because we want to understand the complexity of our code and the resources that it uses. This allows us to create more efficient solutions with our code which in turn allows us to develop better solutions to everyday problems. Big O Notation also helps us share a large amount of information using symbols, so it saves us a lot of time when communicating the complexity of our code to others.
Why do we use Algorithms?
Essentially we use Algorithms because we want to really understand how we are solving problems. Using algorithms makes communicating our solutions to other people a lot more efficient and allows us to transfer the way we solve problems to both other people, machines more effectively.
Why do you need to know Big O Notation?
To pass interviews… that’s about it. Just kidding, actually you need to know it in order to properly communicate information about the complexity of your code as well as to actually understand which algorithms to choose in various situations. You will also need it to successfully succeed at the interview processes of the larger more well known tech companies.
Terms
Time Complexity — Time complexity describes the amount of time an algorithm takes based on the input to the algorithm or the complexity of time inside of an algorithm
Space Complexity — Space Complexity is the amount of space(memory) that an algorithm in regards to the input or amount of space used inside an algorithm
Computational Complexity — Computational Complexity refers to the amount of resources required to run or execute an algorithm(Time, Space(Memory))
Asymptotic — Asymptotic refers to a line that is reaching a specific curve as it gets closer to infinity. That curve basically indicates something. When it comes to algorithms we use Asymptotic analysis to describe the different bounds(where the line approaches) that indicate best, worse and average case as far as resources used by an algorithm goes.
Polynomial — Polynomials are typically used to refer to a combination of terms in Algebra. When it comes to Algorithms, Big O Notation Polynomial-Time refers to Algorithms that are asymptotically analysed as O(nc)
Runtime — Runtime refers to how long it takes for an algorithm to execute a specific number of operations. This is different from execution time in that execution time would include all of the operations not a specific number of them.
Logarithm — Logarithms are usually known as the inverse function of exponents. We use Logarithms in the real world anytime we use interest rates. Logarithms help us find the power that you can apply to an input to get an output. In comp sci Logarithmic algorithms usually a base of 2. Logarithmic complexity in Big O is also known as O(log(n)).
Constant — A constant is usually a fixed value in Algebra. In regards to Algorithms; Constant Time Complexity refers to algorithms that are constantly executed in the same amount of time regardless of changes to the input size.
Linear — Linear in Algebra usually refers to an equation that creates a straight line. When it comes to Algorithms, Time Complexity; Linear refers to algorithms that when Asymptotically analysed, graphed you will see a straight line. Also known as O(n) time.
Quadratic — Quadratic in Algebra usually refers to an equation where the highest exponent is squared. In regards to algorithms, time complexity we can say an Algorithm’s time complexity is Quadratic when it is O(n²) and the performance of the algorithm is based on the square of the input.
Polylogarithmic — Poly refers to a shape with many sides. When we combined poly with logarithmic we get Polylogarithmic. It is just like Logarithmic except instead of being O(log(n)). It’s O(log(n)x) and you would replace the x with k and that represents the many sides.
Exponential — Exponential typically refers to something that grows very quickly or exponentially. In regards to Algorithms this refers to algorithms whose resource requirements or time, space complexity quickly grow as the input size changes. When referring to data, exponential growth is usually a sign that really big changes are occurring really fast.O(c¹) (Replace the one with an n because medium doesn’t support superscript n)
Recursion — Recursion is simply the process of dividing a problem by itself essentially until the problem can be solved by solving the smaller version of itself. When referring to recursive algorithms, what is basically happening is that the problem is being broken into smaller problems until the smallest version is reached and solved. You can learn more about Recursion here in this Recursion video.
