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

equation plotted for c1=32 c2=20 and n=1

  • $\begingroup$ Hint: $1 \leq n \leq n^2$. $\endgroup$ Commented Sep 19, 2017 at 7:38
  • $\begingroup$ n greater then 1 is because the input will always be greater then 0? or is there any other reason for that? $\endgroup$ Commented Sep 19, 2017 at 7:52
  • $\begingroup$ 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. $\endgroup$ Commented Sep 19, 2017 at 7:56
  • $\begingroup$ just wanted to confirm as i was thinking the same. $\endgroup$ Commented Sep 19, 2017 at 7:57

1 Answer 1


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). $$

  • $\begingroup$ 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? $\endgroup$ Commented Sep 19, 2017 at 7:54
  • $\begingroup$ These are high-school inequalities. If you forget about the connection to computer science, I am sure you will be able to prove them. $\endgroup$ Commented Sep 19, 2017 at 7:58
  • $\begingroup$ i plotted it on graph and get this graph as a result, can you please have your expert look. Thanks alot for your patience and help in this regard. I also noticed that the intersection lies between 25 and 30 for the upper bound $\endgroup$ Commented Sep 19, 2017 at 9:05
  • $\begingroup$ I am unable to see any graph. $\endgroup$ Commented Sep 19, 2017 at 9:07
  • $\begingroup$ sorry, added with edits, i used another tool n now its showing the intersection point as 32. $\endgroup$ Commented Sep 19, 2017 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.