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.

I wonder the english explanation of O(n+k). Does it mean, the algorithm will run at most n+k times? Or does it mean the algorithm will run at most n or k times? And also is it same with O(n)+O(k)?

Thank you

share|improve this question
1  
Well, first $O(n+k)$ has nothing explicitly to do with algorithms. However, it is often used to discuss upper bounds on the amount of time an algorithm takes (not "times," which implies you run the same algorithm more than once - I suspect that is an English slip-up there.) –  Thomas Andrews Mar 22 '13 at 19:55
7  
It is a sound made by pigs. –  copper.hat Mar 22 '13 at 19:59
    
@copper.hat funny. Smiley's are hateful, but they help in situations where people speak different languages. You'd be amazed at how differently people hear animal sounds in different languages. eleceng.adelaide.edu.au/personal/dabbott/animal.html –  Thomas Andrews Mar 22 '13 at 21:08
    
@ThomasAndrews: That's interesting! –  copper.hat Mar 22 '13 at 21:36

3 Answers 3

up vote 5 down vote accepted

The English explanation would be that the running time of the algorithm will have an upper bound which has a linear dependency on both parameters n and k.
For example if you double both n and k, the running time will be doubled at most.

Note that O(M) (where M is an expression in terms of n) does not mean that the algorithm runs at most M times. It means that there exists a constant c and $n_0$ such that for $n>n_0$ the running time will be less than $c\times M$

As an another interesting example, suppose an algorithm on a von_Neumann architecture super computer has complexity $2^n +0.5\times n^3 + 0.22 $ which is $O( 2^n)$ while a clever algorithm which runs on a Pentium II PC has complexity $ 230\times n^{100} + 542\times n^2 $ which is $O(n^{100})$
Maybe for small inputs the super computer runs in a glimpse while the poor PC freaks out but there exists a c(related to the hardware structure) and $n_0$(related to the size of input) which the PC runs the algorihms faster than the super computer See also Wikipedia

share|improve this answer
2  
I am considering k as a variable like n. Like some graph theory algorithms which run in O(m+n) –  Zeta.Investigator Mar 22 '13 at 20:25
    
@ThomasAndrews Do you mean that k or n drops out usually because of having less order rather than the other one? Or do you mean O(n+k) is e.g. O(n+5) and is different from O(n+m)? –  Zeta.Investigator Mar 22 '13 at 20:43
    
@ThomasAndrews I edited my post. Did I get the point correctly? –  Zeta.Investigator Mar 22 '13 at 20:55
    
Yes. That looks fine. Will delete my comments. –  Thomas Andrews Mar 22 '13 at 21:02
    
@ThomasAndrews Thank you for your explanations:) –  Zeta.Investigator Mar 22 '13 at 21:03

$f(x) = O(g(x))$ means that $f(x)$ is bounded above by $g(x) \cdot k$ as $x \to \infty$ where k is some positive constant.

This means that $f(x) = O(g(x))$ if and only if there exists some real number $x_0$ such that

$$\lvert f(x)\rvert \leq \lvert g(x) \cdot k \rvert \text{ for all } x \gt x_0$$

share|improve this answer

In graph theoretic algorithms it is very common to have runtime bounds that depend on both the number of edges and number of vertices. For example, $O(E+V \log V)$ would be typical of an algorithm that builds a data structure from the vertices (such as a sorted list) and then accesses the data structure, on average, a bounded number of times per edge.

It is correct that $O(f) + O(g)$ and $O(f+g)$ denote the same class of bounds.

share|improve this answer

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.