Question

Are any of the following implications always true? Prove or give a counter-example.

a) f(n) = Θ(g(n)) -> f(n) = cg(n) + o(g(n)), for some real constant c > 0. *(little o in here)

b) f(n) = Θ(g(n)) -> f(n) = cg(n) + O(g(n)), for some real constant c > 0. *(big O in here)

Answer 1

(n) is nothing but the tighter bound within the two functions.SO lets get started with two points.

a) f(n) = (g(n)) -> f(n) = cg(n) + o(g(n)) for some real constant c > 0.,

Now, considering the above equation f(n) = ((g(n)) is nothing but f(n) = O(g(n)) and f(n) =(g(n)) , so not exactly but in a way we can say f(n) = g(n)

Now, o(g(n)) is nothing but f(n)<g(n) ( here "Little o" means Less Than ) so, by login when we apply to equation

(g(n)) -> f(n) = cg(n) + o(g(n))

f(n) >cf(n) + f(n) (where f(n) = g(n) since f(n) = (g(n)))

So, the statement is false

b)

This question is same as first one but the only difference is big O notation.

Now quickly learn this thing that small o notation is tightly lower bounded and Big O is Lower bound so roughly,

O(n) means less than or equal to

o(n) means less than

so using your equation,

f(n) = Θ(g(n)) -> f(n) = cg(n) + O(g(n)),

f(n)<= cf(n) + f(n)

Therefore it might or might not be true(Depend on the cases)
So rigidly it is False also