Revision as of 00:32, 5 June 2008 by Metafor (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Note on Edit: I changed the notation of the formula for the number of divisors, so people wouldn't be confused by the usage of the letter $n$ in both sides of the equation.

Please put four tides at the end of your message, like this: -- ~~~~. Also, what is $O(n)$? -- 1=2 13:01, 3 June 2008 (UTC)

Sorry about that, hehe. Oh, and I believe that is Landau notation. See this thread and the entry in MathWorld (I did not write the formula, by the way :P). To quote Merryfield:

“As $x \rightarrow ?$, $f(x) = O(g(x))$ iff $\exists C$ such that eventually $|f(x)| \leq C|g(x)|$.”

Basically, $O|g|$ is the upper bound of $|f|$ as $x$ approaches some value; if $f(x) = 3x^{2} + 5$, for example, then $f(x) = O(x^{2})$, because the term $x^2$ ‘grows’ faster than any other term that defines the function (note that this is not an equation; this is merely saying that there is some positive multiple of $|x^2|$ — say, $C|x^{2}|$ — that will always be greater than or equal to the absolute value of the function as $x$ approaches a certain value). Of course, this is a very basic definition of the big-O notation, and may not be so accurate.

-- Metafor 04:32, 5 June 2008 (UTC)