9

What is the time complexity of the MD5 algorithm? I couldn't find a definitive answer online. I think the complexity is O(n) but I'm not really sure.

Carlos Frank
  • 167
  • 2
  • 13
  • 4
    Time complexity of what? What is n? MD5 processes data in blocks of 512 bit, doing 4 rounds of [some internal operation](https://en.wikipedia.org/wiki/MD5#Algorithm) (sometimes it may add one more block to the data - "the message is padded so that its length is divisible by 512"). So, if n is bytes, it does `roundup(8*n/512)` operations which is `O(n)` in Uniform Cost model (real memory hierarchy has nonuniform access cost for different layers/sizes). – osgx Apr 26 '17 at 05:20
  • 3
    Yes, for `n` byte or bits the complexity of MD5 is `O(n)`. – Thomas M. DuBuisson Apr 26 '17 at 14:39

1 Answers1

6

O(n) as mentioned by DuBuisson and osgx in the comments.

Ben Behar
  • 364
  • 3
  • 12