Using the definition of O( big-O), show that 2n $ \in $ O($6n^2$)

73 Views Asked by At

This is the definition of big-O

Let f(n) and g(n) be function from positive integers to positive reals. We say f=θ(g) if there is a constant c>0 such that f(n)≤c⋅g(n)

Down below is my attempt at solving the problem

If we let $f(n) = 2n$ and $g(n)= 6n^2$, then we can apply the definition...

2n < c* $6n^2$

I know this seems like a half hearted attempt, but this was all i could do.

I need someone to give some advice on what to do next here

2

There are 2 best solutions below

2
On

Take $c=1$ and let $N=10$. Then, $$2n < c \cdot 6n^2 \quad \forall n \ge N$$

0
On

We should find $c$ explicitly.

In particular, if $n \geq 1$, then $n \le n^2$, hence $2n \leq 2n^2 \le 6n^2$. Hence we can pick $c$ to be $1$.