Big O notation of a program that takes 10x time for 3n input

Question

I have a program that calculates N digits of Pi.

I have measured that it takes 10x time to calculate 3n numbers, compared with the time for calculating n numbers. The source code also gives an indication for this running times.

For example, if 1000 digits take 0.011 seconds, 3000 digits take 0.11 seconds, and 9000 digits take 1.1 seconds.

What is the Big O complexity of such algorithm?

Edit:

Here's the source code.

Answer 1

We can't be sure, knowing a finite number of values of a function with an infinite domain means there are an infinite number of functions you cannot exclude. To really know how the run time grows, I'd need to analyse the source code.

But if we assume the runtime of the algorithm is exactly equal to t(n) = c * n^x, the sensible solution for x is log(10) / log(3), since that gives the behaviour you describe. Since the constant doesn't matter for big oh notation, my best guess for the runtime is t(n) = O(n^(log(10) / log(3))) which is roughly O(n^2.1).

Answer 2

You can’t say too much from just three data points. It seems to be slightly larger than quadratic. You could make a guess that the time is c * n^k. Or you could make a guess that the time is c * log n * n^2. I’d spend a little time and add at least the next four data points to be a bit more confident.