0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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$
    – David Richerby
    Commented May 31, 2017 at 9:50

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.