A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 5 years ago
For a given function f(n), what is (theta)Θf(n)= (n3/1000)100n2100n+3 ? <Algorithm complexity>Please help me to solve this. Can any kindly help me by giving me access to problems such as these and help solving them? Thanks in advance!
anonymous
 5 years ago
For a given function f(n), what is (theta)Θf(n)= (n3/1000)100n2100n+3 ? <Algorithm complexity>Please help me to solve this. Can any kindly help me by giving me access to problems such as these and help solving them? Thanks in advance!

This Question is Closed

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0its n cube by 1000  100 n square....

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0u know the Onotation?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Omega...yes...But can't understand how to solve problems such as the one above..

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0from the definition, we are looking for constants c1 and c2 such that c1*f(n) is less than the expression and c2*f(n) is greater than the expression (thus forming upper and lower bounds). if we pick a small enough c1 (say .00000001) then I can make n cubed be less than the exression. Like wise, if I make c2 big enough (say 1000000000) I can make it be greater than the expression. thus that expression is theta of n cubed. Now the key realization that makes this problem trivial is that for large n, all the lower order terms become irrelevant and I can always get rid of the constants and low order terms and immediately pick the highest order term. in this case n cubed. what is theta of 50 n4 + 800 n3 + 400 n2 +9000 ? Well its just n4.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.