Search code examples
if-statementfor-loopcomplexity-theory

Algorithm complexity: if/else under for loop

I am wondering if in a situation like the following (an if/else statement under a for loop) the complexity would be O(n) or O(n^2):

for character in string:
    if character==something:
        do something
    else:
        do something else.

Thank you!

Solution

  • It will be

    O(n) if 'do something' and 'do something else' are O(1)

    O(n^2) if 'do something' and 'do something else' are O(n)

    Basically the complexity of the for loop will depend on the complexity of it components and the no. of loops.