patternMinor
Notation for average case complexity of an algorithm
Viewed 0 times
caseaveragealgorithmnotationforcomplexity
Problem
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.
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.
Solution
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.)
Context
StackExchange Computer Science Q#14960, answer score: 2
Revisions (0)
No revisions yet.