# What is O(m+n) and O(m*n) in Big O notation? [duplicate]

I understand that `O(n)` describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. An example of this is a for loop:

``````for n in 0.100
puts n
end
``````

What does the `O(m+n)` and `O(m*n)` mean? I couldn't find any clear examples of this in the internet. Please provide examples! Thanks!

• The possible duplicate provided above doesn't answer this specific question on O(m+n) and O(m*n) – perseverance Sep 9 '15 at 19:54

That depends on the context, but typically, m and n are the sizes of two separate parts of the dataset, or two separate properties of the dataset, for example, filling a m×n array. Usually, when the complexity depends on two independent factors, the second one gets denoted by m.

So we might say that finding the union of two sets is O(m+n), where m and n are the sizes of the inputs, but finding their Cartesian product is O(m·n).

## Code sample:

``````// BOILERPLATE:
#include <array>
#include <iostream>
#include <utility>
#include <vector>

using std::array;
using std::cout;
using std::endl;
using std::ostream;
using std::pair;
using std::vector;

template<class T, class U>
ostream& operator<< ( ostream& s, const pair<T,U>& x);

template<class T>
ostream& operator<< ( ostream& s, const vector<T>& x );

template<class T, size_t N>
ostream& operator<< ( ostream& s, const array<T,N>& x );
// END OF BOILERPLATE.

static const size_t M = 10, N = 5;

int main(void)
{
static const array<int,M> a = {1,2,3,4,5,6,7,8,9,10}; // Inputs.
static const array<int,N> b = {0,4,8,12,16};
array<int,M>::const_iterator i = a.cbegin();  // Iterators.
array<int,M>::const_iterator j = b.cbegin();

vector<int> c;    // This vector will hold our results.

// First, compute the set union of a and b,
c.reserve(M+N);   // Which has at most M + N elements.

while ( i < a.cend() || j < b.cend() ) {
if ( i == a.cend() || *i > *j ) {
c.emplace(c.end(), *j);
++j;
} else if ( j == b.cend() || *i < *j ) {
c.emplace(c.end(), *i);
++i;
} else {
/* We can only have got here if: i and j are both valid and neither *i
* nor *j is greater than the other.  Therefore, they are equal and this
* element is a duplicate.
*/
c.emplace(c.end(), *i);
++i;
++j;
} // end if
} // end while
/* The above loop terminates because it increments i, j or both at each step.
* Provided that a and b are sorted and have no duplicates, it computes the
* set union because it adds whichever of their next elements are smaller
* until both are exhausted.  Since it walks each array to the end once, it
* completes in M + N increment operations.
*/

cout << "The set union of " << a
<< " and " << b
<< " is " << c << endl;

c.clear();    // Done with it.

vector< pair<int,int> > d;

// Now, compute the Cartesian product, which has M*N elements.
d.reserve(M*N);

for ( i = a.cbegin(); i < a.cend(); ++i )
for ( j = b.cbegin(); j < b.cend(); ++j )
d.emplace(d.end(), pair<int,int>(*i, *j) );
// We perform exactly M * N insertions.

cout << "The Cartesian product is " << d << "."  << endl;

d.clear();    // Done with it.

return 0;
}

// MORE BOILERPLATE.  Not needed to understand the algorithms.

template<class T, class U>
ostream& operator<< ( ostream& s, const pair<T,U>& x) {
s << "(" << x.first << ", " << x.second << ")";
return s;
}

template<class T>
ostream& show( ostream& s, const T& x ) {
/* Outputs a human-readable representation of an iterable container whose
* value-type supports stream output to the stream s.
*/
typename T::const_iterator i = x.cbegin();
s << "{";

if ( i < x.cend() ) {
s << *i;
++i;
}

for ( ; i < x.cend(); ++i ) {
s << ", ";
s << *i;
}

s << "}";

return s;
}

template<class T>
inline ostream& operator<< ( ostream& s, const vector<T>& x ) {
/* Outputs a human-readable representation of a vector.
*/
return show(s, x);
}

template<class T, size_t N>
inline ostream& operator<< ( ostream& s, const array<T,N>& x ) {
/* Outputs a human-readable representation of an array.
*/
return show(s, x);
}
``````
• Is it possible for you to give a code example of both O(m+n) and O(m*n)? – perseverance Sep 9 '15 at 19:56
• Okay. There’s a code sample using C++ STL. – Davislor Sep 9 '15 at 22:47

O(n) does not mean time grows linearly with n. It means time is bounded by a line that has some Y-intercept, and some slope times n, like this ... ... no matter how big n gets. The same goes for any other big-O. For example, O(n x m) means there is some bounding curve C1 + C2 x (n x m), and O(n + m) means the curve is C1 + C2 x (n + m).

(Keep in mind that better big-O does not mean better performance, except as n gets large.)

• Correct, but this does not answer the question. – MetaFight Sep 8 '15 at 2:36
• @MetaFight: now it does. – Mike Dunlavey Sep 8 '15 at 12:29
• downvote retracted :). – MetaFight Sep 8 '15 at 12:33
• you're 2 rep points away from 10k. I'll upvote this for you :) – MetaFight Sep 9 '15 at 13:20
• @MetaFight: yippee – Mike Dunlavey Sep 9 '15 at 19:00

They are linear and subquadratic time complexities respectively.

Suppose I've got two sets of data that I am performing some operation. If one set is the same size as the other, it's 2n. If it's anything more or less it's m+n. It's always O(n), we are just making sure to note that there are two independent factors here. We strip out the 2 because big O doesn't care about constants.

Subquadratic time functions similarly but it is dependent rather than independent. For every m, you do n things or vice versa. Thus we do at most n^2 operations. It's in O(n^2) but it's probably going to be less than that but definitely more than O(n) so we use O(m*n) to make that clear.

So in summary, we could just call these O(n) and O(n^2) but in some cases, particularly when comparing very similar algorithms, it's important to have some precision of clarity.

• So to visualize these in code, they would be two `for` loops right after each other, and two nested `for` loops respectively? – user113093 Sep 7 '15 at 23:25
• Yes but with an upper bound rather than a guarantee of being the same size. – World Engineer Sep 8 '15 at 0:18