# Proving big O notation problem

Ok Im a bit new and my mathematical proof knowledge and practice is novice will, its not much as I'm only a few weeks into an algorithm and design paper and am a little learning challenged. I am trying to wrap my head around a several lab question questions and I'm hoping that if someone can help me with this I will build a little momentum and be able to answer the harder ones under my own steam.

I have a definition: Let f, g be functions. If there exist c, n0 > 0 such that,for all n > n0, f(n) ≤ c · g(n), then f(n) is O(g(n))

Have to prove this using the definition.

For every function f : N→N, f(n) is O(f(n)).

Now firstly I'm confused bu the face that g(n) isnt in this question but it is in the harder ones so I know it isnt a typo. I'm thinking that it is the same function so shouldn't it be big theta? I am very confused. Also how to present this as a proof is also quite mysterious to me. Can I do this as a direct proof?

Most appreciate any help.

• If you were asked to show that every function h : N→N is such that h(n) is O(h(n)), you would turn to the definition, assume that f = h, that g = h, and check whether for this choice of f and g, the assertion that "there exist c, n0 > 0 such that,for all n > n0, f(n) ≤ c · g(n)" holds (and then f(n) is O(g(n))) or not (and then f(n) is not in O(g(n))). Well, does it? – Did Aug 28 '17 at 7:44
• Im sorry I found your explanation a little too complicated. Could you explain why you can substitute h in? – F.Horn Aug 28 '17 at 9:25
• Because this is a definition hence, to check that some given sequence h(n) is O(k(n)) for some other sequence k(n), one is supposed to plug in f(n)=h(n) and g(n)=k(n) in the definition and to see if the definition works for this choice of f(n) and g(n) or not. (FYI, I find your "I found your explanation a little too complicated" hilarious.) – Did Aug 28 '17 at 10:47

To show that $f(n)$ is $O(f(n))$, just go back to your definition of "$f(n)$ is $O(g(n))$" and check that it holds with $c=1$, $n_0=1$ (actually $n_0$ can be anything), and $g=f$.
In a similar way you can show $f(n)$ is $\Omega(f(n))$, and thus $f(n)$ is $\Theta(f(n))$.