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.

  • $\begingroup$ 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? $\endgroup$ – Did Aug 28 '17 at 7:44
  • $\begingroup$ Im sorry I found your explanation a little too complicated. Could you explain why you can substitute h in? $\endgroup$ – F.Horn Aug 28 '17 at 9:25
  • $\begingroup$ 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.) $\endgroup$ – 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))$.

  • $\begingroup$ Is how does using the definition that refers to g(n) help prove this? Isnt it a completely different function? $\endgroup$ – F.Horn Aug 28 '17 at 6:28
  • $\begingroup$ In the definition both f and g must be functions, but you don't have any other limitation so you can take the same function both as f and g $\endgroup$ – karmalu Aug 28 '17 at 12:42

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.