CODEWITHSUNDEEP
algorithmproofbig-o
user3068177
user3068177

Reputation: 357

Algorithm Proofs

In this case, f(n), g(n), and h(n) are asymptotically positive functions, which means that there exists an N such that f(n)/g(n)/h(n) > 0, for all n >= N. Given that:

f(n) = Θ(g(n))
g(n) = Θ(h(n))

I need to prove that 

f(n=Θ(h(n))).

It is suggested to use the formal definition of Θ, which states that if f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k. The values of c1, c2, and k must be fixed for the function f and must not depend on n. I have found examples similar to this such but am still unsure as to how to address this problem. Can anyone point me in the right direction?

EDIT: My current guess is to try and use the transitive property, which states if a=b and b=c then a=c. I'm not sure this is exactly correct but it is my best guess for now. The syntax of the f(n=Θ(h(n))) is confusing me the most. I am not completely sure as how to interpret it.

Upvotes: 0

Views: 61

Answers (1)

user3068177
user3068177

Reputation: 357

Assuming that f(n=Θ(h(n))) is the same as f(n) = O(h(n)), then using Big 0 definition, which says:

f = O(g) iff exist c, n0 > 0 such that forall n >= n0 then 0 <= f(n) <= cg(n)
g = O(h) iff exist k, n1 > 0 such that forall n >= n1 then 0 <= g(n) <= kh(n)

then I can divide the last inequality and divide all members by

c: 0 <= f(n)/c <= g(n)

and substitute g(n) with 

0 <= f(n)/c <= kh(n)

then multiply all by c, giving us 

0 <= f(n) <= kch(n)

which is equivalent to f=O(h). So 

f = O(h) iff exist j, n2 > 0 such that forall n >= n2 then 0 <= f(n) <= jh(n)

Upvotes: 1

Related Questions