CODEWITHSUNDEEP
algorithm
michel hamad
michel hamad

Reputation: 1

Is log(f(n)^c)=Ω(log(g(n))) or not

You are given functions f and g such that f(n)=Ω(g(n)). Is log(f(n)^c)=Ω(log(g(n)))? (Here c is some positive constant.) You should assume that f and g are non-decreasing and always bigger than 1.

This a question in my algorithm course and i cant figure out if it's true or false or depending on the constant or depending on the functions f and g

Upvotes: 0

Views: 875

Answers (2)

OmG
OmG

Reputation: 18838

It's straightforward to prove. As f(n) = Omega(g(n)), it means lim{n -> ∞} f(n)/g(n) > 0. As f and g are non-decreasing and greater than 1, and log is an increasing function, lim{n -> ∞} log(f(n))/log(g(n)) > 0. Hence, log(f(n)) = Omega(log(g(n)).

On the other hand log(f(n)^c) = c log(f(n)). As c is a constant factor, log(f(n)^c) is Omega(log(g(n)) as well anf your claim is correct.

Upvotes: 2

lettomobile
lettomobile

Reputation: 316

First, I point out that instead of this notation f(n) = Ω(g(n)) I use this f(n) ∈ Ω(g(n))

From Omega definition we have:

f(n) ∈ g(n) <=> ∃s,k > 0 | f(n) >= s*g(n) ∀n >= k

So for log(f(n)^c) ∈ Ω(c*log(g(n))) we can say:

  1. ∃s > 0 (s=c for easiness) | log(f(n)^c) >= c*log(g(n)) ∀n >= k

Then we have:

  1. c*log(f(n)) >= c*log(g(n)) ∀n >= k

  2. f(n) >= g(n) ∀n >= k

And since we know that f(n) ∈ Ω(g(n)) we can state that log(f(n)^c) ∈ Ω(c*log(g(n))) .

Upvotes: 1

Related Questions