# Relation between best case and average case complexity

I have two questions,

1. Does $T_\mathrm{best}(N) = O(f(N))$ imply that $T_\mathrm{avg}(N) = \Omega(f(N))$?

2. Does $T_\mathrm{avg}(N) = O(f(N))$ imply that $T_\mathrm{best}(N) = O(f(N))$?

Where, \begin{align*}T_\mathrm{best}(N) &= \min \{T_1, \dots, T_N\}\\ T_\mathrm{avg}(N) &= \frac1N \sum_{1\leq i\leq n} T_i \end{align*} for some sequence $T_1, T_2, \dots$.

I think both are true but don’t know how to prove them. Any ideas?

I think your definitions of $T_{\text{best}}$, $T_{\text{worst}}$, and $T_{\text{avg}}$ could use some clarification. I'll proceed assuming the correspond to best-, worst-, and average-case runtimes [1].
The first claim is false. The problem is that $f$ could dominate $T_{\text{best}}$ at an arbitrary rate. So we cannot make any claims about $f$'s status as an asymptotic lower bound of $T_{\text{avg}}$.
The second claim is true. Hint: prove $T_{\text{best}} = O(T_{\text{avg}})$, then use transitivity of $O$ to conclude the result.
• Welcome to the site! As a specific example for the first case, we might have that the actual running time is exactly $n$ steps, for every input. It is true to say that the best case is $O(2^n)$ but the average case certainly isn't $\Omega(2^n)$. May 31, 2017 at 9:50