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!

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

score 13 · Accepted Answer · answered Jul 01 '15 at 15:00

13

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.

answered Jul 01 '15 at 15:00

Deepansh Singh

172
6

7

Okay, this answer was confusing. Both the first and second line have same 'if do.. and something else..' – Rajesh Mappu Nov 26 '18 at 19:40
4

omg- please somebody edit this... why is this marked answer? – Gel Dec 01 '21 at 16:42
This answer is clear and goes straight to the point. – JoJo Jan 27 '22 at 15:23

score 2 · Answer 2 · answered Jul 01 '15 at 15:05

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

answered Jul 01 '15 at 15:05

deceze

491,798
79
706
853

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

score 1 · Answer 3 · answered Jul 01 '15 at 14:57

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.

answered Jul 01 '15 at 14:57

bigC5012

569
1
5
17

Algorithm complexity: if/else under for loop

3 Answers3

Linked