A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

For a given function f(n), what is (theta)Θf(n)= (n3/1000)-100n2-100n+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
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    its n cube by 1000 - 100 n square....

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    please help

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    u know the O-notation?

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Omega...yes...But can't understand how to solve problems such as the one above..

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    from 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.

  6. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.