9

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!

Amateur
  • 139
  • 1
  • 1
  • 6
  • 1
    just O(n). you need recursive algorithms to get Log(N). see : https://en.wikipedia.org/wiki/Computational_complexity_theory – Timothy Groote Jul 01 '15 at 14:56
  • @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. – John Jul 01 '15 at 15:20
  • @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). – Bernhard Barker Jul 01 '15 at 15:31
  • @Dukeling thats a good point :) still, the implication of required recursion for log(n) complexity is not correct anyway :) – John Jul 01 '15 at 15:41
  • possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – Bernhard Barker Jul 01 '15 at 15:44

5 Answers5

11

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.

Deepansh Singh
  • 160
  • 6
4

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).

deceze
  • 510,633
  • 85
  • 743
  • 889
  • 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)`. – Bernhard Barker Jul 01 '15 at 15:35
  • 1
    Imho it would be reasonble to make assumption that doSomething(else) is in fact constant time. – John Jul 01 '15 at 15:45
1

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.

bigC5012
  • 589
  • 1
  • 5
  • 19
0

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).

Fayo Muhe
  • 1
0

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)

BKRavindu
  • 1
  • 1