0
$\begingroup$

If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by putting in values of $c$ and $n_0$ at once or do I have to put in values of c first and then get n on one side and put in values for $n_0$, the for all $n \ge n_0$ confuses me.

$\endgroup$
1
$\begingroup$

It all depends on the case and how easy it is to search $n_0$ or use $c$, in your case you can show that $2n + 1$ belongs to $n^2$, taking the constant $c = 1$, so that in the proof of BigO, $g (n)$ dominates $f(n)$, what is the same $2n + 1 \le c (n^2)\to 2n + 1 \le n^2$; now you can search a $n_0$.

$\endgroup$
0
$\begingroup$

equation here is f(n) < c(n^2), here we have 2 unknowns, a mathematical equation with one unknown can be solved in 1 step, but with two unknowns you have to substitute one with some value to find another one. the number of steps increase with number of unknowns. So No its not possible to do all this in one step. Also definition of big O is intuitive, by proving f(n) < cg(n) we are proving that f(n) does not grow faster than g(n), in our case f(n) is a linear equation, while g(n) is quadratic, its obvious that a quadratic equation will grow faster than any linear equation(meaning linear equation grows like 1,2,3,4,5 while quadratic will grow like 1,2,4,8,16 so on i hope you get my point).

$\endgroup$
0
$\begingroup$

You have to demonstrate that there is one c and one $n_0$ such that 2n+1 <= c $n^2$ for all $n >= n_0$. In this case, 2n+1 <= $3n^2$ for n >= 1, 2n+1 <= 1.25 $n^2$ for n >= 2, 2n+1 <= 7/9 $n^2$ for n >= 3 etc, so there are many combinations for c, n_0.

To prove this, you usually go the easiest way possible. For example 2n+1 <= 2n^2 + n^2 = 3 n^2, so c = 3 and $n_0$ = 1 works. There is no need to find the smallest possible c or $n_0$.

$\endgroup$

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.