0

I wanted to compare the CRC algorithm to the MD5 algorithm for computational complexity. I found the following thread that states that MD5 is O(n).

What is the time complexity of CRC? How does the time-complexity of CRC compare to MD5?

My guess is O(n) as well, since it has to look at all the data to be computed. However, @defines states in his answer that "CRC is computationally much less complex than MD5".

avgJoe
  • 832
  • 7
  • 24
  • It seems that CRC must be O(n) also as its processing time increases or decreases in direct proportion to the input size. – 500 - Internal Server Error Jan 20 '21 at 18:18
  • 3
    They have the same complexity O(n). In the context of what you've read, "complex" means "complicated" and not "computational complexity". – Paul Hankin Jan 20 '21 at 18:38
  • 1
    You can compare the [wiki example](https://en.wikipedia.org/wiki/MD5#Pseudocode) to the crc64c() function in [this answer](https://stackoverflow.com/questions/60270174/60271106#60271106). The CRC can be sped up to be 20 to 30 times faster than crc64c() using XMM registers and carryless multiply (PCLMULQDQ) in assembly. MD5 can only be sped up somewhat by using XMM registers. – rcgldr Jan 20 '21 at 21:12
  • 1
    (The cost increases in proportion with problem size for both: upper bound in O(n), lower bound in Ω(n): cost in Θ(n). The constant factors *do* differ.) – greybeard Jan 20 '21 at 22:11

1 Answers1

3

Yes, CRC is O(n), where n is the length of the sequence. What matters is the constant factor in front of the n.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • yes they both are `O(n)` ... however the CRC32 C++ implementation is 13 lines of code with single for loop using XOR the MD5 is 3 pages of code with sub functions. So the MD5 as much slower from the runtime perspective btw SHA1 is 5 pages long (also `O(n)`) with much more sub-functions so its a magnitude slower than MD5 – Spektre Jan 21 '21 at 07:41
  • 1
    Yes, MD5 and SHA1 and others are slower than a CRC. But it has little to do with the number of lines of code. Often you need more lines of code to make something much _faster_. For example, a bit-wise CRC is 14 lines of code. A byte-wise CRC that is more than ten times as fast is 54 lines of code. A word-wise CRC that's about twice as fast again is 376 lines of code. – Mark Adler Jan 21 '21 at 18:50
  • Yep I know but those implementations are mine with the same coding style doing almost the same things so number of lines + density of sub function calls is sort of metric (as the stuff is pretty similar) however for generic code you're right. Btw the CRC32 implementation is using LUT so its the same speed as bit wise CRC ... – Spektre Jan 22 '21 at 05:43
  • @Spektre I don't understand that last statement. A byte-wise lookup table CRC is about 20 times as fast as a bit-wise CRC. – Mark Adler Jan 22 '21 at 17:07
  • @MarkAdler How do I best quantify the constant factor? By counting operations per byte of data? (I am assuming this to be run on a micro controller without multi-processing capabilities) – avgJoe Jan 22 '21 at 20:10
  • 1
    @avgJoe You can try to count operations, but it is far easier and much more accurate to simply implement them and measure the execution time on your target processor. – Mark Adler Jan 22 '21 at 20:15
  • @avgJoe direct measurement of the runtime on targeted system is the only way as the same code might behave very differently on different computing HW architectures in respect to runtime. – Spektre Jan 22 '21 at 21:46
  • @MarkAdler I taught you got the fastest bitwise CRC so also LUT in mind.... – Spektre Jan 22 '21 at 21:47
  • @MarkAdler - I don' t understand your lines of code comment. A function to generate a table is about 16 lines, and a CRC function that uses the table is about 8 lines. Also why is using a byte wise look up table 20x faster than looping 8 times to cycle 8 bits for every byte processed by a CRC function? – rcgldr Jan 23 '21 at 21:52
  • @rcgldr Yes, you're right. In the olden days, and nowadays unoptimized (-O0), the byte-wise is 18 times as fast as the bit-wise. But with modern optimizers (-O3) it's only four times as fast. – Mark Adler Jan 24 '21 at 02:32
  • @rcgldr I was counting pre-generated tables in the lines of code. – Mark Adler Jan 24 '21 at 02:32
  • @MarkAdler - even with optimization for byte wise table lookup, assembly based "folding" code for CRC using XMM registers and carryless multiply is about 30 times as fast on my system. MD5 could also be sped up somewhat with XMM registers (parallel operations), but no where close to the 30x speed up for CRC. – rcgldr Jan 24 '21 at 18:59
  • @rcgldr Do you have a reference for calculating big O that I could use? – Arash Jun 01 '21 at 20:37
  • 1
    @Arash - you can find table based implementations for CRC doing a search here at Stack Overflow. For the assembly based "folding" code, you can find examples for Windows | Visual Studio at this [github repository](https://github.com/jeffareid/crc). The assembly code is over 550 lines. – rcgldr Jun 01 '21 at 21:03
  • @MarkAdler what is O(64 bit CRC)? by the length of the sequence you mean length of data or CRC bits? – Arash Jun 14 '21 at 06:46
  • How we can relate the complexity to data length? – Arash Jun 14 '21 at 07:54
  • 1
    n is the length of the data. – Mark Adler Jun 14 '21 at 08:14