Question

Are any of the following implications always true? Prove or give a counter-example. a) f(n) =...

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)

Homework Answers

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

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Prove or give a counter example: If f is continuous on R and differentiable on R...
Prove or give a counter example: If f is continuous on R and differentiable on R ∖ { 0 } with lim x → 0 f ′ ( x ) = L , then f is differentiable on R .
Let f,g be positive real-valued functions. Use the definition of big-O to prove: If f(n) is...
Let f,g be positive real-valued functions. Use the definition of big-O to prove: If f(n) is O(g(n)), then f2(n)+f4(n) is O(g2(n)+g4(n)).
Assume that f(n) = O(g(n)). Can g(n) = O(f(n))? Are there cases where g(n) is not...
Assume that f(n) = O(g(n)). Can g(n) = O(f(n))? Are there cases where g(n) is not O(f(n))? Prove your answers (give examples for the possible cases as part of your proofs, and argue the result is true for your example).
Prove the statement true or use a counter-example to explain why it is false. Let a,...
Prove the statement true or use a counter-example to explain why it is false. Let a, b, and c be natural numbers. If (a*c) does not divide (b*c), then a does not divide b.
either prove that it’s true by explicitly using limit laws, or give examples of functions that...
either prove that it’s true by explicitly using limit laws, or give examples of functions that contradict the statement a) If limx→0 [f(x)g(x)] exists as a real number, then both limx→0 f(x) and limx→0 g(x) must exist as real numbers b) If both limx→0 [f(x) − g(x)] and limx→0 f(x) exist as real numbers, then limx→0 g(x) must exist as a real number
NOTE- If it is true, you need to prove it and If it is false, give...
NOTE- If it is true, you need to prove it and If it is false, give a counterexample f : [a, b] → R is continuous and in the open interval (a,b) differentiable. a) f rises strictly monotonously ⇐ ∀x ∈ (a, b) : f ′(x) > 0. (TRUE or FALSE?) b) f is constant ⇐⇒ ∀x∈(a,b): f′(x)=0 (TRUE or FALSE?) c) If f is reversable, f has no critical point. (TRUE or FALSE?) d) If a is a “minimizer”...
Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time...
Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time O(h(g(n))+c), for any constant c >= 0 and any functions g(n) and h(n) where h(n) >= n.
Master Theorem: Let T(n) = aT(n/b) + f(n) for some constants a ≥ 1, b >...
Master Theorem: Let T(n) = aT(n/b) + f(n) for some constants a ≥ 1, b > 1. (1). If f(n) = O(n logb a− ) for some constant > 0, then T(n) = Θ(n logb a ). (2). If f(n) = Θ(n logb a ), then T(n) = Θ(n logb a log n). (3). If f(n) = Ω(n logb a+ ) for some constant > 0, and af(n/b) ≤ cf(n) for some constant c < 1, for all large n,...
Prove or give a counter-example: (a) if R ⊂ S and T ⊂ U then T\...
Prove or give a counter-example: (a) if R ⊂ S and T ⊂ U then T\ S ⊂ U \R. (b) if R∪S⊂T∪U, R∩S= Ø and T⊂ R, then S ⊂ U. (c) if R ∩ S⊂T ∩ S then R⊂T. (d) R\ (S\T)=(R\S) \ T
True or False, explain. If false, give counter example. a) if events A and B disjoint...
True or False, explain. If false, give counter example. a) if events A and B disjoint then A and B independent. b) if events A and B independent then A and B disjoint. c) It is impossible for events A and B to be both mutually exclusive and independent.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT