Question

Show that f(n) = (n^3+2n)/
2n is in O(n2).

Answer 1

I assume you want this for \[n\to\infty\]

Answer 2

and that it is \[O(n^2)\]

Answer 3

yes sorry I missed the ^

Answer 4

show that \[\lim_{n\to\infty}\left|\frac{(n^3+2n)/(2n)}{n^2}\right|<\infty\]

Answer 5

why is it over n^2? b/c of O(n^2)? do you know what that stands for?

Answer 6

I simplified it to (1/2) + (1/n^2)

Answer 7

so at infinity it goes to 1/2?

Answer 8

you want to show that \[(n^3+2n)/ 2n\le Mx^2\] for all x bigger than x_0

it is enough to show that I typed above

Answer 9

yes

Answer 10

I'm still kind of confuse b/c I have the answer to a similar question but the answer is different

Answer 11

it's for like (n2+1)/n

Answer 12

\[(n^3+2n)/ 2n\le Mn^2\]

n>n_0 (not x)

Answer 13

and they choose values for m and n

Answer 14

ok

Answer 15

they reduce it n+(1/n) and then made it n+(1/n)<2n then they choose values for m=2 and k=1 and assume that n>k=1 so they have

Answer 16

f(n)=(n^2+1)/n=n+(1/n)<2n = m*g(n)

Answer 17

and that's the answer which does not make sense at all for me

Answer 18

"f(n)=(n^2+1)/n=n+(1/n)<2n = m*g(n)"

what don't you understand?

Answer 19

I don't see how they got 2n because it was O(n)

Answer 20

O(n) just means that \[(n^2+1)/n\le M n\] for some n (here n apparently greater than 1)

Answer 21

if n>1 then 1/n<n

so n+1/n<n+n=2n

Answer 22

Ohh I see now so for mine n^2/2 + 1

Answer 23

oh wait how do you know n is greater than 1

Answer 24

usually you are looking at it as \[n\to \infty\] so assuming n>1 is no big deal

Answer 25

okay so I simplified to 1/2 and that's <infinity

Answer 26

I think taking the limit is a lot more simplify it's still the same interpretation i assume

Answer 27

you could also do this...

\[\frac{n^3+2n}{2n} =\frac{n^3}{2n}+\frac{2n}{2n}=\frac{n^2}{2}+1<n^2+n^2=2n^2=Mn^2\]

Answer 28

both ways...using the limit or finding an upper bound works

Answer 29

alright thanks so much for your help!!

Answer 30

no problem