For instance if i have an algorithm that is O(n2) and it will run for 10 seconds for a problem size of 1000. Now if i were to double the problem size to 2000 i want to know the approximate run time in seconds. I know the answer for it but i want to understand the logic on how to get to the answer. So here is what i am thinking.
N = 1000 , Therefore 1000^2 = 10 seconds
N = 2000, Therefore (2*1000)^2, // stuck here
Now i am not sure i mean i know it will be 40 seconds because 2 to the power of 2 is 4 and then you multiply the 10 seconds by 4 and get 40 seconds but not entirely sure if this is right thinking. Was wondering if someone can break it down in simple terms?
Best Answer
Complexity classes such as
O(n)
orO(n²)
are not meant to calculate actual running time. Instead, they are meant to compare how different algorithms scale when we change the input size.For example, here we have two algorithms that apply
frobnicate(a, b)
to each matching item:Obviously, the 1st algorithm has
O(n²)
complexity while the second isO(n)
. Therefore, we can conclude thatalgorithm2
scales better for large inputs. But here is anotherO(n)
algorithm:This scales just as well as
algorithm2
but will always be slower! In fact, theO(n²)
algorithm1
will outperform this algorithm for small inputs! Becausealgorithm3
has a fixed 9-second overhead, we can't plug different numbers into theO(n)
complexity formula to find out how long a different input size will take.Example:
In reality, the running time is not possible to reliably calculate. Even if you can figure out a cost for each atomic operation, hardware quirks such as cache boundaries will get in your way. The only reliable option is to do statistical sampling over different input sizes, and then fit an estimation function matching the expected complexity class to the collected data.
Let's assume we have a run time estimation function (!= complexity class) of
f(n) = a·n² + b·n + c
, and let's assume thatb = c = 0
for simplicity (i.e. no linear factors, no constant overhead). Then, we can calculate the parametera
from the data pointf(1000) = 10 seconds
:Therefore,
f(n) = n²/100000 seconds
. If we plug inn = 2000
, we getThis is consistent with the shortcut that if we multiply the input size by
n
(heren = 2
), the output is increased byn²
(heren² = 4
).