I have to find the value of constant factor $c_1$ and $c_2$ and $n_0$ in equation for which this equation satisfy:

$$c_1\leq \frac12 - \frac3n \leq c_2$$

Here $n\geq n_0$.

So for what value of $c_1, c_2 $ and $n_0$, this equation will hold, Please help me out here. This is question of chapter name Asymptotic notation, In korman book it's answer is $c_1 = 1/14$, $c_2=1/2$ and $n_0 =7$ , But I am not able to figure out here how he found that value of $c_1, c_2$ and $n_0$.

Thanks in advance

  • 1
    $\begingroup$ You mean $n \ge n_0$, not $n \le n_0$. $\endgroup$ – Robert Israel Jan 3 '12 at 6:17
  • $\begingroup$ @RobertIsrael I believe the original post has $n\geq n_0$ but Benjamin Lim made a typo in his edit. I have re-edited appropriately. $\endgroup$ – matt Jan 3 '12 at 6:19
  • $\begingroup$ @RobertIsrael: Yaa Robert Thanks $\endgroup$ – Nishant Jan 3 '12 at 6:20

That $c_2=\frac{1}{2}$ is common sense.

You understand that the LHS i.e.$(\frac{1}{2}-\frac{3}{n}) \le \frac{1}{2}$, so take the limit

$\lim_{x \rightarrow \infty}(\frac{1}{2}-\frac{3}{n})=\frac{1}{2}$.

Now, once we fix $c_2$, $c_1$ will depend upon $n_0$. As Robert pointed out,$(\frac{1}{2}-\frac{3}{n})\le 0$ till $n_0\le 6$.Hence we have $n_0=7$ and accordingly $c_1=\frac{1}{14}$.

  • $\begingroup$ How did u get c1=1/14 can you plese elaborate it $\endgroup$ – Nishant Jan 3 '12 at 6:47
  • 1
    $\begingroup$ Assumption: both $c_1$ & $c_2$ are $\ge 0$. The function $(\frac{1}{2}-\frac{3}{n})$ is increasing wrt $n$. If $(\frac{1}{2}-\frac{3}{n}) \ge 0$, it implies $n \ge 2 \times 3$ and the least value of $n \ge 6$ is 6, but the value in bracket is $0$ for $n=6$. So, put $n=7$ in the expression and you have the value $\frac{1}{14}$. As the function is increasing wrt n, its value for all $n \ge 7$ will be $\ge \frac{1}{14}$. Hope this helps. $\endgroup$ – nb1 Jan 3 '12 at 6:56

Hints: 1) What happens as $n \to \infty$?

2) Note that $\frac{1}{2} - \frac{3}{n}$ is increasing for $n > 0$.

3) There isn't a unique answer, but I think $7$ was chosen because it's the least $n_0$ for which you can take $c_1 > 0$.

  • $\begingroup$ here is there way of finding value og n_0, because we can't guess and check for each possible value of n_0 for c_1 > 0 so plese suggest me some way of finding n_0 value $\endgroup$ – Nishant Jan 3 '12 at 6:40
  • $\begingroup$ Can you solve $\frac{1}{2} - \frac{3}{n} = 0$? $\endgroup$ – Robert Israel Jan 3 '12 at 19:17

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.