Menu
Often, some of the answers mention that a given solution is linear, or that another one is quadratic.
How to make the difference / identify what is what?
Can someone explain this, the easiest possible way, for the ones like me who still don't know?
965
It is perfectly possible that for, say, N=1000, a quadratic algorithm is much faster than a linear one. But, if you increase N, you know at some point this will reverse and linear will have the upper hand. Whether the user will want to increase N enough or not, depends on the particular use case.
Quadratic Time Complexity represents an algorithm whose performance is directly proportional to the squared size of the input data set (think of Linear, but squared). Within our programs, this time complexity will occur whenever we nest over multiple iterations within the data sets.
Linear time represents a function that will take a longer amount of time if the input is larger, so the larger the input the larger amount of time it will take.
O(n) constant time can absolutely be faster than O(1) linear time. The reason is that constant-time operations are totally ignored in Big O, which is a measure of how fast an algorithm's complexity increases as input size n increases, and nothing else. It's a measure of growth rate, not running time.
A method is linear when the time it takes increases linearly with the number of elements involved. For example, a for loop which prints the elements of an array is roughly linear:
for x in range(10): print x because if we print range(100) instead of range(10), the time it will take to run it is 10 times longer. You will see very often that written as O(N), meaning that the time or computational effort to run the algorithm is proportional to N.
Now, let's say we want to print the elements of two for loops:
for x in range(10): for y in range(10): print x, y For every x, I go 10 times looping y. For this reason, the whole thing goes through 10x10=100 prints (you can see them just by running the code). If instead of using 10, I use 100, now the method will do 100x100=10000. In other words, the method goes as O(N*N) or O(N²), because every time you increase the number of elements, the computation effort or time will increase as the square of the number of points.
92
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
