Suppose I know that the computational complexity of an algorithm is $\mathcal{O}(f(n))$ where $n$ is the sample size. Suppose I have two data sets with sizes $n_1$ and $n_2$. The data sets have no systematic differences; they are samples from the same population. Both $n_1$ and $n_2$ are large numbers so that asymptotic approximations like $\mathcal{O(\cdot)}$ approximately hold. Suppose I know that it takes $t_1$ seconds to execute the algorithm on the first data set.

Question: Can I say that executing the algorithm on the second data set will take approximately $t_1\cdot\frac{f(n_2)}{f(n_1)}$ seconds?

(I am trying to see whether my understanding of $\mathcal{O(\cdot)}$ is correct in a practical application.)

  • $\begingroup$ this is pedantic, but $\Theta$ might be more appropriate than $\mathcal{O}$ here. and even if the asymptotics hold, of course the approximation can still be off by an arbitrarily large constant factor. $\endgroup$ – shimao Nov 8 '19 at 21:45
  • $\begingroup$ @shimao, could you please elaborate? Would you suggest the answer by Cliff AB is off? $\endgroup$ – Richard Hardy Nov 9 '19 at 5:49

I know the question is about "in practice", so I hope this answer isn't too pedantic, but big-$O$ notation is a pretty blunt tool used by theorists, so proper interpretation is difficult.

Firstly, big-$O$ is an upper bound, so $5n^2+3n \in O(n^2)$, but also $5n^2+3n \in O(n^{100})$. If your algorithm runs in linear time, then its time complexity is in $O(f(n))$ for $f(n)=n^{100}$, which will give you a very weird prediction if you plug this into your expression.

There is also $\Omega$ to denote the lower bound equivalent of $O$, and also $\Theta$, to denote that a function is both asymptotically upper and lower bounded.

However, even $\Theta$ isn't really precise enough to do what you want. For example, consider $T(n) = \begin{cases} p \cdot n^2 \text{ if $n$ is odd} \\ q \cdot n^2 \text{ if $n$ is even}\end{cases}$, where $p$ is an extremely small value (say $10^{-1000}$) and $q$ is extremely large, say $10^{1000}$. Then technically, $T(n) \in \Theta(n^2)$, since it is lower bounded by $pn^2$ and upper bounded by $qn^2$. Therefore, if you plug in $n_1 = 1, n_2 = 2, t_1 = 1, f(n) = n^2$, then you'll get $t_2 \approx 4$, when the actual runtime would be $4 \cdot 10^{2000}$ seconds. While your approximation is still guaranteed to be within a constant factor of $\frac{q}{p}$ of the true runtime for any $n$, that isn't very reassuring.

Of course this is an extremely pathological runtime which you would never see in any real algorithm. Maybe the best real world example I can give is FFT, where a fast $\Theta(n \log n)$ algorithm is available for power of 2 size inputs, but it can be several times more expensive to compute on prime sized inputs.

Finally, it's important to remember that complexity theory makes statements about the runtime of algorithms on idealized abstract machines (typically turing machines or random-access machines). Of course, much of this carries over to "real world" computing, but as Cliff AB points out, real world computing has additional considerations.

  • $\begingroup$ +1 and thank you very much for your answer, it is very helpful. $\endgroup$ – Richard Hardy Nov 9 '19 at 19:55

Generally speaking, yes.

There are several reasons why in practice, a declared $O(f(n))$ may not hold. Note that all these reasons essentially boil down to $O(f(n))$ not being exactly appropriate.

1.) Differing number of iterations required with different sized datasets. It's very easy to evaluate the complexity of a single step of an algorithm. It's really hard to see how many steps will be required to meet your convergence criteria. Often, when authors say "this algorithm runs in $O(f(n))$", they mean "each iteration runs in $O(f(n))$.

Interesting side note: for MLE problems with lots of data and few parameters, it's not too uncommon for the number iterations to decrease with the sample size when using Newton's method. This is because as the sample size increases, the log-likelihood should approach a quadratic function by MLE theory, and functions well locally approximated by a quadratic function should converge quickly with Newton's method.

2.) Memory issues. Again, it is very easy to come up with $O(f(n))$ assuming memory doesn't affect computation. This can mean running out of RAM, swapping L1 cache, whether the data is stored in continguous fashion, data passing between distributed systems, etc. It's basically impossible to know these limitations in advance, so often the author will ignore this when declaring a computational complexity.

Often on small to moderate problems, the memory issues are almost ignorable. On massive datasets, that is certainly not the case. The people I've talked that work on HPC statistical algorithms tell me that for them, the math computations are essentially ignorable, it's the moving of data they need to optimize for better performance.

But in general, yes, using your formula should give you a ballpark estimate of computational time.

  • $\begingroup$ Thank you for your answer! I am aware of memory issues, but I skipped that for brevity. Your comment on the number of iterations until convergence is useful and is something I did not consider enough. If I understand your correctly, it suggests that an important determinant of computational time is simply ignored in $\mathcal{O}(\cdot)$ considerations which are per-iteration by nature. +1 for now. $\endgroup$ – Richard Hardy Nov 8 '19 at 19:18

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.