1
$\begingroup$

I have some questions that I don't understand about time complexity.

  1. Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
  2. Given that the best case complexity of the algorithm $A$ is $O(f(n))$ and the worst case complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
  3. Given that the average case complexity of the algorithm $A$ is $Θ(f(n))$ and the worst case complexity of A is $O(g(n))$. It follows that $f(n) ∈ O(g(n))$.

I will appreciate if you can help me understand those!

Thanks a lot!

$\endgroup$
2
  • $\begingroup$ Thank you! My question is how to prove or disprove statements like this. $\endgroup$ – TheCalc Apr 19 at 16:54
  • $\begingroup$ Sorry, I misread the first statement. It is true after all $\endgroup$ – idmean Apr 19 at 16:58
0
$\begingroup$

The first and the last statements are correct, while the second one is incorrect.

Statement 1

Denote by $T_{min}$ the actual running time of the algorithm $A$, in the best case, and $T_{max}$ in the worst case. By how we chose $T_{min}$ and $T_{max}$ it follows that $T_{min}\le T_{max}$.

From our assumptions, $T_{min}=\Omega(g(n))\implies T_{min}\ge c_1g(n)$. Also from our assumptions, $T_{max}=O(f(n))\implies T_{max}\le c_2f(n)$.

Combining them together we get:

$c_1f(n)\le T_{min} \le T_{max} \le c_2g(n)$, which means that $f(n)\le \frac{c_2}{c_1}g(n)\implies f(n)=O(g(n))$

Statement 2

Consider the following algorithm:

if lst[0] != 0:
    for x in lst:
        print(x)

And consider the inputs $I_1:=[0,1,2,3,...,n]$ and $I_2:=[1,2,3,...n+1]$. Clearly, the algorithm takes $O(1)$ time with input $I_1$, but $\Omega(n)$ time with input $I_2$. Obvoiusly, $n\neq O(1)$ and thus the statement is incorrect.

Statement 3

Repeat the proof of statement 1. Note that also $T_{avg}\le T_{max}$ and thus the proof still holds.

$\endgroup$
1
  • $\begingroup$ Wow - thank you so much! This is very helpful, and I understand everything now! Thanks! $\endgroup$ – TheCalc Apr 19 at 17:39

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.