2

I am trying to fully understand how to get Big-Oh. Consider the following:

Prove f(n) = O(g(n)) 
f(n) = 3n + 2
g(n) = n

According to the rules of asymptotic notation listed here

in order for this to be true: 

3n + 2/n = c, where c is a constant.

this becomes:

3n/n + 2/n

which results in:

3 + 2/n

I know for a fact that f(n) = O(g(n)). However, I do not understand how using the limit method proves this. Moreover, in this other example:

Prove f(n) = O(g(n))
f(n) = 3*n^2
g(n) = n

this is not true, but why? If someone could provide me a step by step explanation I would be grateful. Examples taken from here

user3220348
  • 21

1 Answers1

1

To solve the problems you should first learn the definition and understand it. $f = O(g)$ means that up to constant multiplication, $g$ is eventually greater than $f$. So we relax too strict $∀n\ f(n) ≤ g(n)$ in two ways: we allow it to be up to multiplicative constant, i.e. $∃c\ ∀n\ f(n) ≤ c ⋅ g(n)$, and we are interseted only in asymptotics, we don't mind the finite initial segments: $∃c\ ∃n_0\ ∀n ≥ n_0\ f(n) ≤ c ⋅ g(n)$.

So now we have the following questions:

  1. Is eventually $3n + 2 ≤ c ⋅ n$ for some $c$?
  2. Is eventually $3n^2 ≤ c ⋅ n$ for some $c$?

Why? Why not?

user87690
  • 9,133