1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hint: $1 \leq n \leq n^2$. $\endgroup$ – Yuval Filmus Sep 19 '17 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$ – Shahensha Khan Sep 19 '17 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$ – Yuval Filmus Sep 19 '17 at 7:56
  • $\begingroup$ just wanted to confirm as i was thinking the same. $\endgroup$ – Shahensha Khan Sep 19 '17 at 7:57
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Shahensha Khan Sep 19 '17 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$ – Yuval Filmus Sep 19 '17 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$ – Shahensha Khan Sep 19 '17 at 9:05
  • $\begingroup$ I am unable to see any graph. $\endgroup$ – Yuval Filmus Sep 19 '17 at 9:07
  • $\begingroup$ sorry, added with edits, i used another tool n now its showing the intersection point as 32. $\endgroup$ – Shahensha Khan Sep 19 '17 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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