Proving big O notation statement

Question

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.

Answer 1

Perhaps you are puzzled by the fact that the statement you are trying to prove uses only one function, namely f, while the definition you quote involves two different functions.

That being said, the statement you are trying to prove is that every function from N to N does not asymptotically grow faster than itself, what is not so surprising. For a formal proof, let f : N -> N be such a function.

Let c := 1 and n0 := 0; let n be an integer such that n > n0. Then we obtain

f(n) = 1 * f(n) = c * f (n) <= c * f (n)

which, by definition, means that f in O(f), which was the statment to be proved.

This is a direct proof which is carried out by explicit choice of c and n0 from the definition and showing that they satisfy the condition from the definition.

As this is apparently a homework question, I suppose it is given as an example to introduce the formal definition and how to work with it, and not so much because the statement itself is interesting.