# Some problems on Asymptotic Notation.

0 like 0 dislike
113 views

edited

Here, you will get to know how to solve problems in asymptotic notation.

## 1 Answer

0 like 0 dislike
by (562 points)
selected

Best answer

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≥n0

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)2 -5+4+5log5+5≤4(5)2

⇒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) =12n2+6n is O(n3)  and y(n) .

Solution:

Given that,

f(n) =12n2+6n

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

⇒n≥n0

⇒kn3​​​​​​≥12n3+6n​​​​​​2≥12n2+6n

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

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

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

⇒12n2+6n≥12n2≥kn

Therefore, f(n) =y(n)

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

Solution:

Given that:

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

We need to prove

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

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

4n2-64n+288≥n2

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

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

⇒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)=7n3+50n2+200

Solution:

Given that ,

f(n)=7n3+50n2+200

According to Big-oh notation

f(n)≤k.g(n)

|7n3+50n2+200|≤7n3+50n2+200

⇒|7n3+50n2+200|≤7n3+50n3+200n3

⇒|7n3+50n2+200|≤257n3

⇒|7n3+50n2+200|≤257|n3|

⇒f(n)=7n3+50n2+200

⇒k=257

⇒g(n)=n3

Therefore, 7n3+50n2+200=O(n3)

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