[Solved]: Notation for average case complexity of an algorithm

Problem Detail: 

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.

Asked By : Ronald

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14960

3.2K people like this

 Download Related Notes/Documents