# What is the runtime complexity of the BLAKE2 hash function?

Assume you want to calculate the blake2 hash function for an arbitrary input of $$n$$ bytes. I am wondering about the runtime, in particular:

1. Does the runtime of scale linearly with the input length, i.e., can the runtime of blake2 be estimated as O(n)?
2. Is the landau even something that is sensible here, given how optimized cryptographic operations are on modern day processors (say on an intel-i7)

Blake2 takes (in either variant) the input, processes it in fixed-size blocks, padding the last block with zeroes to the full block size if required. The processing operation happens in constant time (it takes a constant number of cycles, big-O notation is meaningless since the input size is fixed). The initialization and finalization steps also take constant time. Therefore, the overall operation takes $$O(n)$$ time.

Blake2 and many other popular hash functions exploit parallelism. So while theoretically the time complexity is $$O(n)$$ but practically you'd see something like this for Blake2b on 2017 Intel Core i7-8700; 6 x 3200MHz; bitvise, supercop-20190910

bytes Cycles/Byes Total Cycles
8 53.8 430
64 6.7 428
576 3.57 2016
1536 3.50 5376
4096 3.18 13025

As you can see, for smaller input size, cycles dont scale linearly but for larger sizes it nearly does.

PS: I listed third quartile measurements for cycles/bytes.

• Big O notation is asymptotic, and doesn't count wall time, it counts the number of operations. Parallelizing an algorithm doesn't decrease its big-O complexity. Sometimes the distinction does get made, but typically using an alternate notation. Jan 28 at 21:10
• @SAIPeregrinus Thanks for that. Edited to phrase it better. Jan 28 at 21:18
• Big-O notation is confusing for many people. It's even worse when cryptographers talk about "constant time" to mean "constant cycle count" and not $O(1)$, since something can be "constant time" by the Big-O meaning but still have varying cycle counts. Or can have constant cycle counts per input byte/block (so cryptographic "constant time" but $O(n)$ complexity (asymptotic linear time). Or worse, since "constant cycle count" really depends on the input values and doesn't care about the input length. So you could have a cryptographic constant-time O(2^n) algorithm. Jan 28 at 21:23