CODEWITHSUNDEEP
python-3.xindexingtime-complexity
Amrinder Kaur
Amrinder Kaur

Reputation: 1

Time complexity of the python3 code below:

if val in my_list:
    return my_list.index(val)

'in' operator has an average complexity of O(n). index() has a complexity of O(n) at worst case. Then is the complexity of these two lines of code exponential i.e. O(n^2) ? or O(n) ?

Upvotes: 0

Views: 45

Answers (2)

Nathaniel Ford
Nathaniel Ford

Reputation: 21230

Generally speaking, if you have two O(n) operations, it will only become O(n^2) if the latter operation happens each time the former operation runs. In this case, the if is a branch - either you go down the True evaluation branch or the False evaluation branch.

Therefore, you have either:

if val in my_list -> evaluates to false, takes O(n) to check each element
End, because there is nothing else to do here. Total of O(n).

Or

if val in my_list -> e evaluates to true, takes O(n) to check each element
my_list.index(val) -> find the index, takes O(n) to check each element
End. Total is O(n) plus O(n)

Compare this to:

for i in my_list:
    if i % 2 == 0:
        print("Index of even number is {}", my_list.index(i))

Here we are iterating through the list, and on each element we might re-iterate through the whole list. This would be O(n^2). (Facilely; in actuality this is O(n log n) because we know that index() will never go past the current index. It's kind of hard to contrive an example where this actually reaches exponential using index.)

Upvotes: 1

Moritz Makowski
Moritz Makowski

Reputation: 382

Assumed that List is replaced with a valid variable name, it should be O(n) (as Nathaniel mentioned). The in operation runs on average n/2 times and in some cases the index operation runs again on average n/2 times. -> O(n) + O(n) = O(n)

Why don't you use a for loop over the indexes themselves?

Upvotes: 1

Related Questions