Question

Is there an easy way to find the C and k of the Big O notation in Discrete Mathematics?

Answer 1

not sure what C and k are
as i recall \[f(x)=O(g(x))\] if
\[\lim_{x\to \infty}\frac{f(x)}{g(x)}=M\]

Answer 2

hmmm interesting. I've never seen that equation. But here's what I know, "we say that f(x) is O(g(x)) if there are constants C and k such that \[|f(x)| \le C|g(x)|\] whenever x >k

Answer 3

I understand the concept but I'm having a hard time figuring out how to find the C and k in a simple way

Answer 4

ok they say the same thing really
divide by \(|g|\) and they are equivalent

Answer 5

i seriously doubt there is one method to solve for all \(f\) and \(g\)

Answer 6

Oh ok. thanks! :)

Answer 7

Another question! "Show that \[7x^2\] is \[Ox^3\]"

Answer 8

in the solution, when x >7, they had 7x^2 < x^3

Answer 9

Is it a trial and error to come up with the value of k?

Answer 10

i must have confused big o notation with little o notation
i would not have said that was correct, so i was wrong
in any case i guess big O means the function is bounded above by the other function, not that they grew at the same rate
in any case you can do it by trial and error
it is clear that \(x^3\) grows faster than \(x^2\) right?

Answer 11

Yes!

Answer 12

or rather grows faster than \(7x^2\)

Answer 13

well then there is not much to this
if \(x=7\) then \(7x^2=7^3\) and \(x^3=7^3\) they are equal when \(x=7\)
if \(x>7\) then \(7x^2<x^3\)

Answer 14

we can try another if you like, but this example seems pretty straight forward

Answer 15

Oh whew I didn't realize that it was that easy lol. Sure! we could try another one. I found 2 problems.
1) Show that x^2 + 2x +1 is O(x^2)
2) Show that 4x^2 +2x +! is 0(x^4)

Answer 16

*2) 4x^2 +2x +1

Answer 17

for what value of \(x\) is \(x^2+2x+1>x^2\) ?

Answer 18

actually \(x^2+2x+1=o(x^2)\) as the limit is one

Answer 19

oh maybe i got this one backwards no matter
\[x^2+2x+1\leq C(x^2)\]for some value of \(C\) we could pick a C less than 1, say \(\frac{1}{2}\)

Answer 20

then since
\[\lim_{x\to \infty}\frac{x^2+2x+1}{x^2}=1\] oh crap C>1 in any cases, find some number for which
\[\frac{x^2+2x+1}{x^2}<2\]

Answer 21

probably a small number will do, like 3