3
$\begingroup$

I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis.

For example, I have tested my algorithm and fitted the results to the curve $f(n)=2.65\times 10^{-15}\cdot(2.17^{n})$ and in my report right now I'm saying something like:

the average case complexity was found to be $\approx 2.65\times 10^{-15}\cdot(2.17^{n})$,

but I would rather say something like

the average case complexity is $\in \Theta(2.17^{n})$.

But I'm not sure if this is technically correct because the result hasn't been theoretically proven, only empirically tested and fitted to the curve.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If you haven't proved something formally, I wouldn't refer to it with Big-Oh as average case complexity. I think (but have no experience to back this up) that it would probably be better if you said something like "for our empirical results, the average running time for instances of a fixed size grew roughly order of $2.17^n$". If you say that the algorithm is in $\Theta(2.17^n)$, then people will expect a proof for this. $\endgroup$
    – G. Bach
    Commented Oct 9, 2013 at 17:51
  • 1
    $\begingroup$ I, too, would advise against using big-O notation to characterize this. It is intended for asymptotic complexity, which you cannot reason about here (at risk of over extrapolating). Curve fitting is different than determining a model. Using this analysis to produce a model is faulty, since you can only look at a limited interval (small relative to $[0,\infty]$). For instance, your observed exponential runtime might become linear or constant in the asymptotic case. That said, you could say that the complexity was measured to be $\approx T(n)$ on interval $I$ (no big-O). $\endgroup$
    – mdxn
    Commented Oct 9, 2013 at 18:38

1 Answer 1

Reset to default
2
$\begingroup$

The notation $\Theta(f(n))$ isn't reserved for worst-case complexity, it's asymptotic notation applicable to functions in general. So you can state that the average case complexity is $\Theta(2.17^n)$, and it means exactly what you think it does. (Regardless of whether this has been proved or not.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ His question was not specifically concerned about the average case complexity itself, but rather the notation used for a statistical (empirical) estimation of. $\endgroup$
    – mdxn
    Commented Oct 9, 2013 at 18:24
  • 4
    $\begingroup$ I'd write “we conjecture that the average complexity is $\Theta(\alpha^n)$ with $\alpha \approx 2.17$”, unless the conjecture is really that the complexity is $\Theta((217/100)^n)$. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Oct 9, 2013 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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