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.

[1] https://en.wikipedia.org/wiki/Best,_worst_and_average_case

  • 1
    $\begingroup$ 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)$. $\endgroup$ May 31 '17 at 9:50

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.