can chernoff bounds be used for proving upper bounds as well as lower bounds

Question

I have a hw problem where it is asked to show theta(n) using chernoff bounds. I am able to prove for O(n) but not in the reverse way.Is it possible to prove both bounds using chernoff?

Answer 1

It looks like it works in both directions. I never used it in the case of lower bound, but here Chernoff bound you can find example of usage as lower bound.

Let $X_{1}, ..., X_{n}$ be independent Bernoulli random variables, each having probability $p > 1/2$. Then the probability of simultaneous occurrence of more than $n/2$ of the events has an exact value $P$.

The Chernoff bound shows that P has the following lower bound.

$P \geq 1 - e ^{-2n(p-\frac{1}{2})^2}$