1

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!

  • 1
    The linked question does not answer this question, unless maybe one must follow the links to get the answer (which makes its accepted answer a bad answer). – user22815 Sep 9 '15 at 16:53
  • 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
6

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
6

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 ...

enter image description here

... 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.)

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

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

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