# how to find upper bound and lower bound of quadratic equation

I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields same results. Anyhow now I am writing the upper and lower bound for that, the equation which I get is

$$20n^2+11n+1$$ I need to find the

$$c_1n^2 \leq 20n^2+11n+1 \leq c_2n^2$$

Here I am stuck and needs some assistance, I have gone through a lot of examples, books, and youtube videos, but no one has any method to solve it instead of assumption and different ways. Any help is much appreciated.

EDIT Graph for the equation • Hint: $1 \leq n \leq n^2$. – Yuval Filmus Sep 19 '17 at 7:38
• n greater then 1 is because the input will always be greater then 0? or is there any other reason for that? – Shahensha Khan Sep 19 '17 at 7:52
• Your algorithm operates on some input whose length is $n$. Can an array have negative length? Can it have length zero? Can it have non-integer length? Try thinking beyond the formulas. – Yuval Filmus Sep 19 '17 at 7:56
• just wanted to confirm as i was thinking the same. – Shahensha Khan Sep 19 '17 at 7:57

Since $n \geq 1$ (since $n$ is the input length), we have $$20n^2 \leq 20n^2 + 11n + 1 \leq (20+11+1)n^2 = 32n^2.$$ Put differently, for all $n \geq 1$, the function $f(n) = 20n^2 + 11n + 1$ is bounded from below by $20n^2$ and from above by $32n^2$. This shows that $f(n) = \Theta(n^2)$.
Note also that when $n$ is large, $f(n)$ gets very close to $20n^2$. Indeed, $$1 \leq \frac{f(n)}{20n^2} \leq 1 + O\left(\frac{1}{n}\right).$$
• in this case the c1=32 and n is 1, and for the c2 how do we solve it. Also i see you adding $n^2$ to 11 and 1, is it assumption that it still is greater or there is any reason behind this? – Shahensha Khan Sep 19 '17 at 7:54