What is it?
Big-O notation is the most common way of comparing the Algorithm Complexity between different Algorithms. It refers to the mathematical function that describes the order of magnitude of the functions executed on each data point .
When using Big-O, is also known as the worst case scenario of an algorithm, which can be affected by how the data is presented â if itâs sorted, distinct, etc.
Understanding Big-O
To write a Big-O notation of any mathematical function describing an algorithm, one would just consider the element of highest order.
Big-O is not a direct translation of the time itâll take to run an algorithm. The time needed to run any step is directly dependent on the hardware and on the data size .
A bigger Big-O value means that the algorithm is more complex, taking more time to run.
Finding Big-O
To discover the Big-O notation of any given algorithm, one need to analyze the operation done in the code.
-
No repetition
For any code that doesnât contain a repetition structure, like the
for loopor a Recursion, with no dependency of the input data, the Big-O notation is . -
Single repetition
A code that walks through every single data point, performing a given procedure, only once, can be considered .
The sum property
Every time a code block follows another independent code block, each Big-O notation is summed. However, a sum doesnât change the order of the Big-O function.
-
Nested repetition
Nested repetition structures walk through every single data point for every data point. So afor loopinside anotherfor loopresults in
The multiplication property
A nested code block inside another code block creates a dependency relationship between blocks. In this case, each Big-O notation in multiplied. For a number of nesting , the Big-O notation is .
Recursive complexity
To find the time complexity of a recursive algorithm, one can follow some steps:
-
Calculate the complexity of a single function call
-
Find how many times the recursion is called for each object
-
Calculate