Question

Algorithm problem

7 [Problem3-4] Let ƒ(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

e ƒ(n)∈O((ƒ(n))^2).

f ƒ(n)∈O(g(n)) implies g(n)∈Ω(ƒ(n)).

g ƒ(n)∈Θ(ƒ(n/2)).

h ƒ(n)+ o(ƒ(n))∈Θ(ƒ(n)).

Answer 1

Definitions:-

Definition of big-O :-

If f(n) and g(n) are two functions such that f(n) <= c.g(n) , where c>0 for all n>=n₀, n₀>=1 then we say that f(n) = O(g(n)).

Definition of big-Omega :-

If f(n) and g(n) are two functions such that f(n) >= c.g(n) , where c>0 for all n>=n₀, n₀>=1 then we say that f(n) = (g(n)).

Definition of big-Theta :-

If f(n) and g(n) are two functions such that f(n) = O(g(n)) and f(n) = (g(n)) , then we say that f(n) = (g(n)).

Definition of small o :-

If f(n) and g(n) are two functions such that f(n) < c.g(n) , where c>0 for all n>=n₀, n₀>=1 then we say that f(n) = o(g(n)).

e). f(n) O((f(n))²)

This is clearly False

For example suppose f(n) = 1/n then (f(n))² = 1/n²

clearly f(n) >= c.(f(n))² => (1/n) >=c.(1/n²)

however reverse will never be true because if 1/n² has to be atleast equal to 1/n then c has to be n but c is a constant not a function.

Therefore , above is FALSE

f). ƒ(n)∈O(g(n)) implies g(n)∈Ω(ƒ(n)).

ƒ(n)∈O(g(n)) => f(n) <=c.g(n) ( from definition of big-oh)

above can be written as c.g(n) >= f(n) => g(n) >= (1/c)f(n)

Let (1/c) = c1 then g(n) >=c1.f(n)

above clearly satisfies definition of big-Omega

g(n)∈Ω(ƒ(n)). is TRUE

Therefore , above is TRUE

g). ƒ(n)∈Θ(ƒ(n/2)).

This is clearly a False

Suppose f(n) = 2²ⁿ then f(n/2) = 2ⁿ

clearly 2²ⁿ >= 1.2ⁿ therefore 2²ⁿ = Ω(2ⁿ)

but reverse will be never true because if 2ⁿ has to be atleast equal to 2²ⁿ then c has to be 2ⁿ but c is a constant not a function.

so, 2²ⁿ != O(2ⁿ) is also TRUE

since 2²ⁿ = Ω(2ⁿ) is true but 2²ⁿ = O(2ⁿ) is not true

Therefore , above is FALSE

h). ƒ(n)+ o(ƒ(n))∈Θ(ƒ(n)).

o(f(n)) means a function which is functionally smaller than f(n).let that function be h(n).

f(n) + h(n) > 1.f(n) (because left side is clearly greater than right side)

so , f(n) + h(n) = Ω(f(n)) is True.....say statement 1

we know from theorem that f(n) + h(n) = O(max(f(n) , h(n))

and it is given that max(f(n),h(n)) = f(n)

so , f(n) + h(n) = O(f(n)) is also true.....say statement 2

from statement 1 and statement 2 , we can conclude that ƒ(n)+ o(ƒ(n))∈Θ(ƒ(n)). is also true.

Therefore, above is TRUE.