The completeness effect in cryptology is where each output bit is a complex function of all the input bits, that is to say that each output bit relies on each and every input bit.
In terms of formal logic, a function f(x) has a good completeness effect if:
-for each bit j, 0 <= j < m in the ciphertext output vector
-there is at least one pair of plaintext vectors X and Xi which differ only in bit i, and for which f(X) and f(Xi) differ in bit j
The completeness effect along with the avalanche effect are critical in the design of modern block ciphers. The avalanche effect ensures that small changes to input make large changes to output, which means even if a brute force attack tries a key very close to the true one, it gets a result that makes little to no sense. The completeness effect ensures that every output bit depends on all the input bits. These two effects prevent "divide and conquer" attacks to the cipher.