9

this may be a silly question, but I want to calculate the complexity of one of my algorithms, and I am not sure what complexity to consider for the memmove() function.

Can you please help / explain ?

void * memmove ( void * destination, const void * source, size_t num );

So is the complexity O(num) or O(1). I suppose it's O(num), but I am not sure as I lack for now the understanding of what's going on under the hood.

Andrei Ciobanu
  • 12,500
  • 24
  • 85
  • 118
  • 1
    The correct answer is probably that it is implementation dependent. You can imagine an unusual system where memory is really some complex graph or linked list. In every real system I'm aware of it is proportional to num. – President James K. Polk Apr 25 '10 at 21:29

2 Answers2

11

Since the running time of memmove increases in direct proportionality with the number of bytes it is required to move, it is O(n).

Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
  • 7
    O(n) is the correct asymptotic complexity, but I don't think I would use the term "direct proportionality" in this context, even for something as simple as `memmove`. Consider n=4 vs. n=1 bytes on a 32-bit architecture: the n=1 case might actually be the more expensive operation! – Jim Lewis Apr 25 '10 at 21:42
  • It's `O(n)` where `n` is the count passed to `memmove()` - but that might not be proportional to the `n` that you're using to characterise your algorithm. – caf Apr 26 '10 at 00:05
2

What are you applying the memmove() operation to - selected elements in the algorithm or all of them? Are you applying memmove() to elements more than once?

Those are the things that will matter to the algorithm's complexity.

That answer may be different that the complexity of memmove() itself regarding the arrays of char elements that memmove() deals with (for which memmove() is an O(n) operation).

Michael Burr
  • 333,147
  • 50
  • 533
  • 760