SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
113 views
in Examples, Exercises and Projects by (562 points)
edited by

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

1 Answer

0 like 0 dislike
by (562 points)
selected by
 
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)


Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...