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?


Here's the source code.


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).

  • Normally the answer is clear by looking at the source but if I'm following his code right this is a case of a function which converges with repeated iterations and that precludes simply pulling out the loops to get the answer. Seeing O(n^2.1) feels so wrong but I think it's right. Feb 8 at 4:58
  • Remember, big O is not a measure of performance. It's an upper bound for performance. Big O is a member of a family of notations. Be sure you're using the right one. Feb 8 at 5:46

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.