Algorithm complexity: if/else under for loop

Question

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!

Tildy

just O(n). you need recursive algorithms to get Log(N). see : en.wikipedia.org/wiki/Computational_complexity_theory – Happen

@Timothy groote that is not correct. Every recursive algorithm can be implemented iteratively in turing complete languages. Therefore, you said that op needs iterative algorithm for log(n) but at the same time your comment implies only recursive. This is contradiction. – Winburn

@user3360241 I'm pretty sure Turing completeness does not mean languages need to be able to have iterative algorithms (but yes, any recursive algorithm can be implemented iteratively, although perhaps in a different language). – Flavoprotein

@Dukeling thats a good point :) still, the implication of required recursion for log(n) complexity is not correct anyway :) – Winburn

possible duplicate of Plain English explanation of Big O – Flavoprotein

Answer 1

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.

Janellajanelle

Okay, this answer was confusing. Both the first and second line have same 'if do.. and something else..' – Intercross

omg- please somebody edit this... why is this marked answer? – Remission

This answer is clear and goes straight to the point. – Samothrace

Answer 2

Put simply, O(n) basically means the algorithm will take as much time to execute as there are elements in n. O(1) means the algorithm always takes a constant time, regardless of how many elements are in the input. O(n^2) means the algorithm takes number of items squared time (i.e. slows down more and more the bigger the input is).

In your case you're doing the same kind of thing for every item in the input once. if..else is just one normal statement you do to each item once. It does neither increase nor decrease the runtime/complexity. Your algorithm is O(n).

Necrophilia

As correctly noted in the other answer, do something( else)? doesn't necessarily need to be O(1), thus the algorithm isn't necessarily O(n). – Flavoprotein

Imho it would be reasonble to make assumption that doSomething(else) is in fact constant time. – Winburn

Answer 3

It depends what you are doing in the else statement, but I believe it is O(n) because worst case you go through the string n times.

Luck

Answer 4

its just 0(n) nothing else because in the evaluation if statement you are just evaluating the truthy of the condition which is constant so constant times any order is that order .for example O(n)*constant is O(n) .so the answer would be O(n).

Numen

Answer 5

The time complexity of the given code snippet is O(n), where n is the length of the string. The code iterates through each character in the string using a loop. For each character, it performs a comparison (character == something) which takes constant time. Therefore, the time complexity of the loop is directly proportional to the length of the string, resulting in a linear time complexity of O(n).

 for character in string:<----------(n)
      if character==something:
          do something<---------------(constant time)-c
      else:
          do something else

time complexity = cn = O(n)

Basham