Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.