SHA-3 (Unkeyed Hash Functions One-Way Hash Functions)

Time Complexity

$O(n)$

Space Complexity

$O(b+d)$ auxiliary? bits

(only need constant padding, O(b)-bit "absorb" state being manipulated, constant-sized non-linear functions (i.e. operating on O(1) bits), and O(d)-sized "squeezed" state being manipulated. In practice b, d are O(1))

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2015