Calculating O(n^3) if we know O(n) runtimetime?

Question

If I have a program that runs over some data in O(n) time, can I semi-accurately guestimate the O(n^3) runtime from my O(n) run?

**O(n) = 5 million iterations @ 2 minutes total runtime**


**O(n^2) = ??**

(5 million)^2 = 2.5+13

2.5+13 / 5 million = 5 million minutes

5 million / 60 = 83,333 hours = 3,472 days = 9.5 years


**O(n^3) = ??**

(5 million)^3 = 1.25e+20

1.25e+20 / 5 million = 2.5e+13 minutes

2.5e+13 / 60 = 416666666667 hours = 17361111111.1 days = 47,564,688 years

Answer 1

Technically knowing O(...) doesn't tell you anything about any execution time for specific finite inputs.

Practically, you can make an estimation for example in the way you did, but the caveat is that it will only give you the order-of-magnitude under the assumptions that 1. the constant scaling factor omitted in the O(...) notations is roughly 1 in whatever units you chose (number of iterations here) in both programs/algorithms and 2. that the input value is large enough so that higher-order terms omitted by the O(...) notation are not relevant anymore.

Whether these assumptions are good assumptions will depend on the particular programs/algorithms you are looking at. It is trivial to come up with examples where this is a really bad approximation, but there are also many cases where such an estimate may be reasonable.

If you just want to estimate whether the alternate program will execute in a non-absurd time frame (e.g. hours vs centuries) I think it will often be a good enough for that, assuming you did not choose a weird unit and assuming there is nothing in the program that would explicitly increase the asymptotic scaling, like e.g. an inner loop with exactly 10000000 iterations.

Answer 2

If I have a program that runs over some data in O(n) time, can I semi-accurately guestimate the O(n^3) runtime from my O(n) run?

No.

There is no the O(n³) runtime, nor either any the O(n) time. Asymptotic complexity speaks to how the behavior of a particular program or subprogram scales with input size. You can use that to estimate the performance of the same program for one input size from appropriate measurements of the performance of that program for other input sizes, but that does not give you any information about any other program's specific performance for a given input size.

In particular, your idea seems to be that the usually-ignored coefficient of the bounding function is a property of the machine, but this is not at all the case. The coefficient is mostly a property of the details of the program. If you estimate it for one program then you know it only for that program. Forget programs with different asymptotic complexity: two programs with the same asymptotic complexity can be constructed that have arbitrarily different absolute performance for any given input size.