Some problems on Asymptotic Notation.

P:1) Show that f(n) +g(n) =O(n²) where f(n) =3n²-n+4 and g(n) =nlogn+5

Solution:

We know that, 'O' is called 'Big-oh'  notation where  O is defined as

 f(n) =O(g(n))  only if there is positive constant C and where f(n) ≤c.g(n), n≥n₀

In the given problem, we have to prove that , 

f(n) +g(n) =O(n²) 

where, f(n) =3n²-n+4 , g(n) =nlogn+5

Hence, we can write it as :

⇒3n²-n+4+nlogn+5 <4n² , where n≥5

Therefore, by taking n=5

⇒3(5)² -5+4+5log5+5≤4(5)²

⇒75-5+4+5log5+5≤100

⇒74+8.49≤100

⇒82.49≤100

f(n) +g(n) =O(n²) 

Hence , proved. 

P:2) Define the function f(n) =12n²+6n is O(n³)  and y(n) . 

Solution:

Given that, 

f(n) =12n²+6n

Let, k>0 be a constant, Consider n₀=(12+6) /k

⇒n≥n₀

⇒kn³​​​​​​≥12n³+6n^{​​​​​​2}≥12n²+6n

therefore, f(n)=O(n³) 

To show, that f(n) =y(n) let k>0 be any constant. 

Consider, n₀=k/12 , for all n≥n₀ 

⇒12n²+6n≥12n²≥kn

Therefore, f(n) =y(n) 

P:3) Show that f(n)=4n²-64n+288=y(n²)

Solution:

Given that:

f(n)=4n²-64n+288

We need to prove 

4n²-64n+288=y(n²)

we can prove that by writing above equation in following form,

4n²-64n+288≥n²

where, n≥1(As per the definition of y)

⇒4(1)²-64(1)+288≥(1)²

^{⇒4-64+288≥1}

^⇒228≥1

^{Therefore, 4n²-64n+288=y(n²)}

^{Hence,proved.}

P:4) Find big-oh notation and little oh notation for ,f(n)=7n³+50n²+200

Solution:

Given that ,

f(n)=7n³+50n²+200

According to Big-oh notation

    f(n)≤k.g(n)

|7n³+50n²+200|≤7n³+50n²+200

⇒|7n³+50n²+200|≤7n³+50n³+200n³

⇒|7n³+50n²+200|≤257n³

⇒|7n³+50n²+200|≤257|n³|

⇒f(n)=7n³+50n²+200

⇒k=257

⇒g(n)=n³

Therefore, 7n³+50n²+200=O(n³)

The liitle oh notation is f(n)=O(n⁴)

---