Question

1.)Prove that f(n) = Ω(g(n)), given: F(n) = n² ; g(n) = n² + n

2.)Prove that f(n) = θ(g(n)) for f(n) = n² + n; g(n) = 5n²

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

1)

Given f(n)=n^2 and g(n)=n^2+n

So, by definition of big Omega f(n)=Omega(g(n)) iff f(n)>=c*g(n)

So,

n^2>=c*(n^2+n)

So, take c=1/2 and n0=1

So,

We ccan say for c=1/2 and n>=n0=1 f(n)=Omega(g(n))

2)

f(n)=n^2+n and g(n)=5*n^2

So,

First we have to prove

f(n)<=c*g(n)

(n^2+n)<=c*(5*n^2)

c=2/5 and n0=1

So, it holds

f(n)=O(g(n))

Now work for omega

We need to prove

(n^2+n)>=c*(5*n^2)

So, c=1/5 and n0=1

So, we can say

f(n)=Omega(g(n))

Hence by definition of theta

f(n)=theta(g(n))

Kindly revert for any queries

Thanks.