Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What does the term $o(k^2)$ in $f(k)=k^2/2+o(k^2)$ mean ?

I have used the asymptotic notation only in context of algorithmic complexity.

With an analogy that, I am guessing it says $f(k)$ returns a value as great as $k^2/2$, and has another term that is at least of degree 2. But then it wouldn't be giving much info on $f(k)$, it could be of any order.

What i make out of $k^2/2+O(k)$ is $k^2$ is the term with the highest degree.

Thanks in advance.

EDIT: I would also appreciate sound references to the topic.

share|cite|improve this question
Presumably you want $f(k)$, or $f(x)=\frac{x^2}{2}+o(x^2)$. Context determines whether we are thinking of $x$ getting very large, or $x$ approaching $0$. In the "large" case, it means that $f(x)=\frac{x^2}{2}$ plus an error term $E(x)$ such that $\lim_{x\to\infty}\frac{E(x)}{x^2}=0$. In the $x$ approaching $0$ case, it is similar, except the limit is as $x\to 0$. – André Nicolas Jan 2 '13 at 23:29

Maybe you mean that $f(k)=\frac{k^2}{2}+o(k^2)$, or that $f(x)=\frac{x^2}{2}+o(x^2)$. However, it is possible that you really do want $f(x)=\frac{k^2}{2}+o(k^2)$, where $k$ is some explicit function of $x$.

In any case, the expression is incomplete. We should really be writing something like $f(x)=\frac{x^2}{2}+o(x^2)$ as $x\to\infty$, or $f(x)=\frac{x^2}{2}+o(x^2)$ as $x\to 0$. However, this bit of additional information is often left out, because it is determined by the context. Because of the word "asymptotic" in the title, I will assume that "as $x\to\infty$" is meant.

In that case, the expression means that $$f(x)=\frac{x^2}{2}+E(x),$$ where $E(x)$ is an "error" term and $$\lim_{x\to\infty}\frac{E(x)}{x^2}=0.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.