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?
can chernoff bounds be used for proving upper bounds as well as lower bounds
0
$\begingroup$
probability-theory
probability-distributions
-
0What is the context? For eg, what is the hw problem? – 2012-03-12