The Great, Big-O-Notation and Javascript: A Never-ending tale of Time and Space Complexity — Part 1*
*This article is a multi-part series.
If we want to add up to a given number in Javascript, let’s say we add up to 6,
6 + 5 + 4 + … + 1 = 21
We can come up with different solutions. The most common would be using a for-loop as given below. But there is another solution, which is using a maths formula,
n * (n + 1) / 2.
Let’s code in JS and find out which is better. 6 is minuscule for addition. So let’s boost up our input say, 1 Billion (1,000,000,000)
So, which is a better solution, Is it the fastest, Is it more readable, Is it less no of lines? I ran both and found that the second solution using the Factorial formula is the fastest.
Not just simply faster than solution 1, But solution-2 significantly faster than solution-1.
Result:
While a performance test gives us a picture of what is happening in our code, Even performance tests vary on the same machine at different times. So think about different machines. Also, the result values are so insignificant (0.0000XXX milliseconds), we cannot calculate the accurate result and define a statement (whether the solution-2 is performance-wise better or time-wise better than solution-1), because the result varies at different times in the single machine itself.
So Big-O-Notation comes to play here.
What is a Big-O-Notation?
“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.”
— Wikipedia’s definition of Big O notation
In Simple words, Using Big-O-Notation, instead of calculating time vs performance, we calculate no. of operations that a computer does for a given code. For example, Addition, Subtraction, Division, Assignment, Comparison are operations performed by a computer.
Let us see how the Big-O-Notation evaluates our code,
Solution-1 and the Big-O:
Solution-2 and the Big-O:
Solution-1 have, 5n + 2 operations while Solution-2 has 3 operations. Operations remain constant regardless of Time or Space (same machine at different times or different machines at the same time).
Also, The performance of Solution-1 varies proportionally as the size of n grows. Performance of Solution-1 is significantly better for n=1000 than n=1000000000. But the Performance of Solution-1 out weights Solution-2 regardless of the size of n.
So if we want to compare two or more solutions for a particular coding problem, We don’t want to do a deeper analysis like the above frequently. It would cost us significant time and energy.
But roughly we can find that solution-2 is better than solution-1 by counting the number of operations a code does to solve the particular problem. We are focusing on the Big Picture and This big picture is called the Big-O-Notation.
Author: Sreenivasa Rajiv
