Help understanding notation and proof

Question

I recently started taking an algorithms class and I am having some trouble following some of the notation and a subsequent proof.

Firstly the notation in question is:

$\exists c > 0 \exists n_0 \forall n \geq n_0 : f(n) \leq cn^2$.

I read it as: There exists some constant $c$ that is greater than zero, (here is where I have trouble) and some $n$ which is greater than or equal to all $n_0$ where $f(n) \leq cn^2$. I sort of have trouble interpreting the first two parts of statement $\exists c > 0$ and $\exists n_0 \forall n \geq n_0$.

I then need to prove something by induction, but as I can't interpret this statement correctly I am having trouble following the inductive step.

Answer 1

The expression $$\exists c > 0 \exists n_0 \forall n \geq n_0 : f(n) \leq cn^2$$ reads as

There exists $c$ greater than $0$, there exists $n_0$ and for all $n$ greater than or equal to $n_0$ then $f(n)$ is less than or equal to $cn^2$.

The interpretation should be that there exists a positive $c$ and some $n_0$ such that for all $n$ greater than $n_0$ (that is, for $n$ "big enough") then $f$ evaluated at $n$ is upper bounded by $cn^2$.

Answer 2

I would parse it in strict form as follows:

There exists $c$ > 0 such that: [ There exists $n_0$ such that: [ For all $n$ $\geq$ $n_0$ : $f(n)$ $\leq$ $cn^2$ ] ]

Alternatively, one can generally group successive uses of the same quantifier, leading to the following:

There exists $c$ > 0 and $n_0$ such that: [ For all $n$ $\geq$ $n_0$ : $f(n)$ $\leq$ $cn^2$ ]