-2

g(n) ≤ c × f(n), for every n ≥ n0, for some c and n0, is it also true that g(n) ≤ c' × f(n), for every n, and some c'?

I said it's false because the definition of Big-Oh is true since n starts form n0. g(n) cannot go over cf(n) for every n ≥ n0, but g(n) can go over if it's every n making the definition of Big-Oh false.

I wonder if I correctly answered it.

JayKay9
  • 31
  • 2
  • Possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – Am_I_Helpful Oct 05 '15 at 13:07

1 Answers1

1

Let's look carefully at the given statements:

  • ∃ n0 ∃ c≥0 (∀ n ≥ n0) (g(n) ≤ cf(n)) (1)
  • ∃ c'≥0 ∀ n (g(n) ≤ c'f(n) (2)

// where "∃ means there exists" and "∀ means for all".

So the question is: if (1) is true is (2) also true? To see that this is not the case take g(n) = 1 and f(n) = n-100. You can see that (1) is correct for n0 = 101 and c = 1 but for (2) if you take n=0 you can't find such c' ≥0 that 1 ≤ c'*(-100). That means that for those f and g (1) is correct but (2) is not. So you are right.

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
sve
  • 4,336
  • 1
  • 19
  • 30