What does O(n+k) mean verbally 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
 A: 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 
A: $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$$
A: 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.
