Table of contents
Before we dive into what Big O notation is, first of let's look at what an algorithm is. An algorithm, is a step by step instruction on how to solve a problem. We can say it's a finite process that if followed will often lead to a solution to a problem.
lets say we have a question
(1+1) * 10 / 2 = x
find x
solution:
(1+1) * 10/2 = x
2 * 10 / 2 = x
2 * 5 = x
10 = x
The value of x is 10.
The above process is an algorithm that got us to find the value of x.
So what is Big O notation?
Big O notation which is also known as algorithmic efficiency is the analysis of an algorithm, It is used to examine the time and space in which an algorithm runs even as the input dataset approaches infinity. Big O notation is focused on representing the worst case scenario of an algorithm. In the words of Ned Batchelder it's "how your code slows as the data grows". The "O" stands for "Order of" and "N" represents The amount of data.
When an algorithm takes more time to run we call it Time complexity, When an algorithm takes more space we call it space complexity.
Under listed are some symbols and their meaning:
0(1) - this is constant time. This Describes an algorithm that will always execute in the same space and time regardless of the amount of the input data set.
O(n) - Linear complexity This Describes an algorithm whose performance is directly proportional to the amount of input data set.
O(n^2) - Quadratic complexity This describes an algorithm whose performance is directly proportional to the square of the input data set.
O(log N) Logarithmic complexity This Describes an Algorithm where time increases Linearly as the input data set
O(2 ^ N) Exponential complexity
This Describes an Algorithm whose performance doubles which each addition to the input data set.
Note: In Big O we often ignore the constants (because its often not the worst case scenario), (A constant is any step that doesn’t scale with the input to the function) It simply means that it (constant) basically remains the same without increasing with the rest of the algorithm no matter what.
Below is link to a Video of Ned Batchelder explaining Big O. https://www.youtube.com/watch?v=Ee0HzlnIYWQ