how does IF affect complexity?

Question

Let's say we have an array of 1.000.000 elements and we go through all of them to check something simple, for example if the first character is "A". From my (very little) understanding, the complexity will be O(n) and it will take some X amount of time. If I add another IF (not else if) to check, let's say, if the last character is "G", how will it change complexity? Will it double the complexity and time? Like O(2n) and 2X?

I would like to avoid taking into consideration the number of calculations different commands have to make. For example, I understand that Len() requires more calculations to give us the result than a simple char comparison does, but let's say that the commands used in the IFs will have (almost) the same amount of complexity.

Answer 1

O(2n) = O(n). Generalizing, O(kn) = O(n), with k being a constant. Sure, with two IFs it might take twice the time, but execution time will still be a linear function of input size.

Edit: Here and Here are explanations, with examples, of the big-O notation which is not too mathematic-oriented

Answer 2

Asymptotic complexity (which is what big-O uses) is not dependent on constant factors, more specifically, you can add / remove any constant factor to / from the function and it will remain equivalent (i.e. O(2n) = O(n)).

Assuming an if-statement takes a constant amount of time, it will only add a constant factor to the complexity.

A "constant amount of time" means:

• The time taken for that if-statement for a given element is not dependent on how many other elements there are in the array
• So basically if it doesn't call a function which looks through the other elements in the array in some way or something similar to this
• Any non-function-calling if-statement is probably fine (unless it contains a statement that goes through the array, which some language allows)

Thus 2 (constant-time) if-statements called for each each element will be O(2n), but this is equal to O(n) (well, it might not really be 2n, more on that in the additional note).

See Wikipedia for more details and a more formal definition.

Note: Apart from not being dependent on constant factors, it is also not dependent on asymptotically smaller terms (terms which remain smaller regardless of how big n gets), e.g. O(n) = O(n + sqrt(n)). And big-O is just an upper bound, so saying it is O(n⁹⁹⁹⁹) would also be correct (though saying that in a test / exam will probably get you 0 marks).

Additional note: The problem when not ignoring constant factors is - what classifies as a unit of work? There is no standard definition here. One way is to use the operation that takes the longest, but determining this may not always be straight-forward, nor would it always be particularly accurate, nor would you be able to generically compare complexities of different algorithms.