Question

Let h(n) = n3 − 8n2 + 75. Give a careful proof, using the definition on page 48, that h(n) is in Ω(n2).

Answer 1

Big-Omega(Ω) is defined as if there are two functions f(n) and g(n) such that f(n)=Ω(g(n)) then, for some constant 'c' and some n0 f(n)>=c.g(n)>=0 for all n>=n0.

Here h(n) = n³-8n²+75

Now for h(n) to be Ω(n²) the following equation should hold for some constant 'c':-

n³-8n²+75>=cn²

Dividing both sides by n² we get:-

n-8 + (75/n²) >= c

Assuming n is only integers for n>=9 the term 75/n² tends to 0. Hence n0 is 9.

Now the equation becomes:-

9-1>=c

0r,

c<=8.

Hence for c<=8 and n0=9 the equation holds hence proved.