What is the time complexity of the RC4 encryption & decryption algorithms? I'm trying to figure out what the time complexity of RC4 encryption &amp; decryption algorithms is, in big-O-notation.
Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit.

So:

 c = m ⊕ G(k)
 m = c ⊕ G(k)


Where c is ciphertext, m is plaintext, G is the RNG and k is the key.

As such, all stream ciphers should be O(n) against the length of input data.