# Time complexity of algorithms

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!

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

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.

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