Question

For a given function f(n), what is (theta)Θf(n)= (n3/1000)-100n2-100n+3 ? 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!

Answer 1

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

Answer 2

please help

Answer 3

u know the O-notation?

Answer 4

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

Answer 5

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.