I have not looked at big O notation since about 1997 so I was hoping for a little sense check.

Imagine a simple algorithm that brute force hacks Caesar Cipher encrypted text. It uses a simple Caesar Cipher algorithm that is nested inside a for 1 to 26 loop, using the loop counter as a key, and outputs all possible results, one of which will be the decrypted plain text.

Would the complexity of this be O(N) (as opposed to O(N²) ?)

I'm fairly sure it's O(N). I know nested loops can increase the order of complexity by N² but the number of times it needs to repeat is fixed at 26. If anything the order of complexity could be described as O(N 26)?

CodePudding user response：

The answer becomes obvious as soon as you explicitly state the meaning of your N in O(N). And the only plausible meaning for N in your case is the length of the input string.

Big-O notation is about the asymptotic increase of run time (sometimes also applied to memory consumption) with increasing input size (however you define that "size").

So, if you define the translation of one character to comsume 1 "time unit", then your algorithm will do 26*N translations, plus some (more or less) constant overhead C, so it's 26*N C time units. In Big-O notation, we ignore any constant factors and additions, and come to the final result of O(N).

Bonus answer:

If were were also interested in the algorithm's behaviour with different-sized alphabets (e.g Chinese), with the alphabet's size being M, you'd get M*N C time units, denoted as O(M*N).

CodePudding user response：

I think you're right: as you have a constant number of keys, this outer loop doesn't account for more complexity: O(26*N) = O(N), as constants are ignored in big O.