# 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$. Sep 19, 2017 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? Sep 19, 2017 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. Sep 19, 2017 at 7:56
• just wanted to confirm as i was thinking the same. Sep 19, 2017 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? Sep 19, 2017 at 7:54