CODEWITHSUNDEEP
pythonwindowsmathtime-complexitycomputer-science-theory
AlmostAcademic
AlmostAcademic

Reputation: 21

What could be the possible cause of this inconsistent time complexity?

I have created a script that requires a number of calculations to be performed. I am currently performing valuation of it's time complexity and there appears to be a few inconsistencies when the number of calculations are low.

The calculations are fairly simple and I would expect the time complexity to be linear however, up until the ~20 000 calculations the execution time seems to double, regardless of how many more calculations are performed. The only difference between each iteration of running the code is the number of calculations i.e the number of loops entered and all that other jazz is the same

After about 20 000 calculations we can see that the relationship conforms to a linear trend. What could be the potential causes for this? I have a limited understanding of computer science, but my limited knowledge brain is thinking it could have something to do with my CPU clock speed being 2.1MHz - but this is probably a coincidence. The data is attached below, including a graph of the overall time complexity. What could be happening at the start when the calculations are low? All help is appreciated! Thank you

Number of Calculations Execution Time (s)
100 1.0739
1000 1.5066
5000 1.7258
10000 1.8882
15000 2.0061
20000 2.1536
25000 2.4743
35000 3.1681
50000 4.9021
75000 7.7399
100000 8.9756
500000 42.1814
1000000 82.0846
5000000 416.8664
7500000 624.5523
10000000 825.1506

Data Graph of Data Graph2 of Data

Upvotes: 1

Views: 120

Answers (1)

templatetypedef
templatetypedef

Reputation: 373402

This might be due to the function’s runtime being a linear function with a very large intercept term. For example, suppose your function’s runtime is T(n) = n + 100000. Then if you start looking at ratios of the form T(2n) / T(n), you’ll see values of the form

(2n + 100000) / (n + 100000) = 1 + n / (n + 100000).

For small values of n, this will be much, much less than 2, even though the “canonical hallmark” of a linear function is that it roughly doubles as n doubles. However, as n increases, the second term gets closer and closer to 1, and eventually the ratio approaches 2.

As for what might cause this, that could be anything from a slow program startup time due to loading a large binary, or the overhead of an interpreter starting up, or the cost of calculating some huge table, etc. But without seeing the code and workflow it would be hard to say which.

Upvotes: 2

Related Questions