I don't think I'm understanding Big O notation. I'm looked up its definition:

T(n) is O( f(n)) if there exists constants c, n-not > 0 such that T(n) <= f(n) for all n > n-not.

I have to make sure f(n) <= c * g(n).

I'm just not sure how to apply this to an actual problem.

For example, in this problem, where log is base 2:

logf(n) is O(log(g(n)))

I have to either prove the statement is correct or give a counter-example that disproves it's correct.

Based on the formula above, I started out with this:

logf(n) <= log(c*g(n))

Assuming I'm placing the constant in the correct location (I wasn't sure about that), I then do this:

logf(n) <= log(c) + log(g(n))

However, I don't know where to go from here or if this is the correct line of reasoning.

Can anyone help explain big O through the use of this problem? I've found the solution to my problem online but it doesn't explain the process clearly enough.

EDIT: This problem was solved below, but it's not really conducive to my learning.

Another problem from this review sheet would be this:

f(n^2) is O(g(n^2))

Like before, I do this:

f(n^2) <= c * g(n^2)

However (like before...) I cannot tell if there are functions that cause this to fail.

  • $\begingroup$ Without more info on f and g this is not true in general. $\endgroup$ – Jean-François Gagnon Oct 2 '15 at 3:02
  • $\begingroup$ Yes, that was the given solution, but it doesn't really explain anything in detail. $\endgroup$ – NotAStudentForReal Oct 2 '15 at 3:04
  • $\begingroup$ You need to find f and g such that for every c there is n-not such that the inequality does not hold. I suppose 2^2^n and 2^n should do the trick. $\endgroup$ – Jean-François Gagnon Oct 2 '15 at 3:07
  • $\begingroup$ Is finding something to disprove the big O problem just a matter of knowing what to look for? By that I mean recognizing what values would cause the inequality to become false? $\endgroup$ – NotAStudentForReal Oct 2 '15 at 3:10
  • $\begingroup$ It is a little more complicated. You need to prove that for any constant c then there exists a n sufficiently large such that the inequality does not hold. $\endgroup$ – Jean-François Gagnon Oct 2 '15 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.