Question

O-notation

Answer 1

http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

Basically it grows as a multiple of log_2(x)

Answer 3

that's just it, I reeeeally don't get the big O notation. As far as I know it shows that one function is bigger than another for very large values?

Answer 4

Essentially, I've always interpreted it as saying that f(x) "grows like" whatever is inside the O, or that it "behaves like" whatever is inside the O, it seems to be an almost intentionally vague definition.

Answer 5

More formally, it seems to be, saying that
\[|f(x)| \leq M|\log_2(x)|\] for some multiple M. We can't say much about what f actually looks like, but we do know that it is bounded by this function.

Answer 6

so the function is a multiple of \(\log_{2}x \)?

Answer 7

Not necessarily, it just needs to be eventually less than or equal to a multiple of log_2 x it's sort of like a general asymptote (if you will).

Answer 8

However, that being said, supposing that f(x) = log_2(x) + 5, we would be able to show that f(x) <= log_2(x) + 5log_2(x) = 6 log_2(x), so f(x) <= M log_2(x) as required. Thus, f(x) = O(log_2(x))

Answer 9

Or f(x) might be constant. Like f(x) = 3. Then, f(x) <= 3log_2(x) and f(x) = O(log_2(x)) again.

Answer 10

But if f(x) = x^2, x^2 will always outperform log_2(x). Thus, f(x) is not in O(log_2(x)) in this case.

Answer 11

*more precisely x^2 always eventually outperforms log_2(x)

Answer 12

\(\log_4(x)\) is \(\mathcal{O}(\log_2(x))\)
also \(\log_2(x)\) is\(\mathcal{O}(\log_4(x))\)

Answer 13

\[\log_ax = \frac{1}{\log_b a}\log_bx = C\log_b x\]

so the base doesn't matter as pointed out by jvatsim

Answer 14

ok, so I think I'm beginning to understand this a little bit. I f I had two functions f(x) and g(x) and I said \(f(x) \le O(g(x))\), then all that means is that for large values of x, there exists a constant M, if multiplied by g(x), it will make the product greater than f(x)?

Answer 15

Other than the "less than sign" looks good. The definition is
\[f(x) = O(g(x))\] if there exists an M such that \[|f(x)| \leq M|g(x)|\] for all \[x > x_0\] (basically it satisfies the inequality eventually).

Answer 16

I did not mention that last part at first in our conversation because I didn't want to add confusion. :)

Answer 17

so is there like a criteria for M, like does it have to be an integer or something, because if there isn't then I could say the opposite is true as well...and that seems like a silly notion

Answer 18

M must be a positive real number. :)

Answer 19

Yes, that would be a problem... good insight.

Answer 20

oh, n by the way...thanks...for not wanting to confuse me, as confused as I was, miraculously that was the one thing I did know about big-O notation

Answer 21

Great!

Answer 22

if it works both ways, whats the point?