This content originally appeared on DEV Community and was authored by chinedu | ddevguys
Big(O) is the way in which we compare algorithmic complexities of two programs in a standard manner
Big(O) is an algorithmic complexity metric, which defines the relationship between the number of input and the steps taken by the algorithm to process those inputs.
In summary big(O) measure, the amount of work a program has to do as the input scales. Big(O) in other can be used to define both time and space complexities
Table of Big(O) starting from best case scenarios to worst case scenarios.
HOW TO CALCULATE TIME COMPLEXITY USING BIG(O)
CONSTANT COMPLEXITY O(1)
In a constant complexity, the steps taken to complete the execution of a program is always the same regardless of the size of its input.
An execution would be getting an element at a certain position in an array(like getting the alphabet D at the index of 3 in the array).
The above takes just one step to complete. The above example, the getAlphabetAt method gets a particular element at a constant position in an array.
No matter how many Alphabet there are in the array the getAlphabetAt method always performs two steps.
First, get the element at a certain position.
Second,
console.logs()the result to the console.
Hence, we can say. The complexity is constant as it doesn’t scale with the input.
LINEAR COMPLEXITIES O(N)
In algorithms with linear complexity a single unit increase in the input causes a unit increase in the steps required to complete the program execution.
An example would be calculating power of every element in an array.
This would be linear because as the array grows it would do one unit more of more of that element.
The above method getCubicValues() will take 3 steps to complete.
So, for each of them in the array passed as a params to getCubicValues() method, the method finds the cube of each of the item in the array and then logs it to the console.
Functions with linear complexity is represented by straight-line graphs increase in position directions.
QUADRATIC COMPLEXITY
In an algorithm with quadratic complexity, the output steps increase quadratically with the increase in the inputs.
In the above graphical example, the getProductValue method multiplies each element in that array with other elements.
There are two loops, where the outer loop it rates through each item, and for each of the item in the outer loop, and the inner loop also iterates over each item.
This makes the number of steps to be N*N where N is the number of elements in the array
BIG(O) NOTATION FOR SPACE COMPLEXITY
In other to get the space complexity, we calculate the amount of space needed by the algorithms for the input element.
BEST VS WORST CASE SCENERIOS IN COMPLEXITIES
There are two types of complexities
Best case scenarios
Worst case scenarios
BEST CASE SCENARIOS
This is the complexity of an algorithm in an ideal situation.
An example would be, let’s say we want to search for an item A in an array of N items.
In the best-case scenarios, it would be that we found the item at the fist index in which we can say the complexity would be an O(1).
WORST CASE SCENARIOS
In the worst case, lets assume we find the item at the nth index (last) in this case we can say the complexity would be an O(N) where N is the total number of items in the array.
In summary, and to round it all up, Algorithmic complexities are used as a tool to measure the performance of an algorithm in terms of time taken and space used.
Thank you for sticking with me through this. You Rock.
If you enjoyed pls follow me on Twitter and Instagram , if there are any improvements or code errors do let me know in the comment section below or send a dm.
Thanks once again and bye for now. Much Love❤❤❤.
This content originally appeared on DEV Community and was authored by chinedu | ddevguys
chinedu | ddevguys | Sciencx (2021-06-26T18:06:49+00:00) Big(O) Notation summarized!. Retrieved from https://www.scien.cx/2021/06/26/bigo-notation-summarized/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.