The Brief Explanation About The Big-O Notation.
Believe me, I’m serious about it.
In terms of programming, when we write a lot of code, especially a function, did we ever wonder how much time it takes to complete our task? Also when the input is growth, how much space does it take in our memory? This complexity problem is called time and space complexity. And here The Big-O Notation comes.
The Big-O notation or O(N) in mathematical function is the way to describe how our algorithm performs as input growth in time. Let us imagine that we write a simple function to do for looping with an input as parameter how many looping we wanted and print its result (of course you can use your favorite programming language, but for me, JavaScript is ‘OK’). When we insert a small input and run our function, it will take a short time to complete its task. And what happens when we increase its input and add another parameter (for example we want to do a mathematical operation inside the loop)?
The two things will happen, our function will either take a longer time or more memory to execute it. This relationship is called time and space complexity and we can analyze it using The Big-O Notation or O(N). The O represents order of complexity of our function and N represents number of our inputs. There are some relationship terms in The Big-O Notation such as constant complexity, linear complexity, etc. I will not mention it all but I will discuss some of it.
#1st, Linear Complexity or O(N)
Let’s imagine we write a function to print each element inside an array, and it takes an exact 1 to 1 relation between time to execute and the number of input, meaning that when the input is doubled, the time to execute it will double too. This relation is called Linear Complexity.
#2nd, Logarithmic Complexity O(log N)
This relationship happens when we implement a binary search to a sorted array. Binary search is a technique used to search for an item in a sorted data sets. It starts by dividing half portion of data by selecting it middle element of data sets (essentially the median), then comparing it to other elements until we narrowed down the possible location of value that we desired (for better explanation you can visit this link). Also, this algorithm performs better with a large number of inputs.
#3rd, Constant Time O(1)
When we want to get a single element of array by its index (arr[index]), no matter large or big it array the amount of time is used to get a single element of array will be the same. This relationship is known as Constant Time.
#4th, Quadratic O(n²)
What happens when we do a for loop inside a for loop? The time and input relation will be quadratic. Meaning that the performance will proportional with square size of input data sets or the performance will increase by the number of inputs rise by the power of 2.
Then, something will be more complex when we try to find a possible combination of each element in data sets or array, that the exponential relationship comes, O(2^n). And there is more term of relationship in The Big-O notation and I will not discuss it here. So, What is the point of knowing it all? As a developer, I think it will help to better understand how our code performs and to make it more efficient by considering space (memory), run-time or execution time and overall performance.
Let me know if you had another info about it. Thank you.
References :
https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/
