Using .index() inside the loop.

Using .index() inside the loop.

Anton Pogrebenko (guest) 26 Nov 2014 21:01

Hi,
Can i use a build-in function .index() inside the loop or is its big-O-notation o(n) so it changes the big-O-notation of whole algorithm to o(n^2) ?

Yuval (guest) 27 Nov 2014 07:00

Even if it's O(n), in this case it is counted as O(1) because the string is of constant and independent length, which is the 26.

Yuval (guest) 27 Nov 2014 07:02

… letters of the ABC

Amir Rubinstein 27 Nov 2014 09:33

Yuval - your answer is correct.
index() is indeed O(n) in the worst case for a list of size n, because Python must linearly go over all the elements in.
However, when the list is of constant size, this becomes O(1).

tal (guest) 27 Nov 2014 19:10

so if i use a function like lst.count ( on inconstant length) in a loop that is constant it's O(n) too, right?

Amir Rubinstein 28 Nov 2014 10:18

What do you mean by "loop that is constant"? A loop that runs a constant number of times? A loop that performs a constant number of operations each iteration?

Guest (guest) 28 Nov 2014 13:54

can i assume, that the list input is from the form ['b','c','d','r','a'] that each lst[i] is from type string? , and not [b,c,d,r,a],(in the example it was like this (the command list("bcdra") turn is to ['b','c','d','r','a'] ) , thanks

Amir Rubinstein 30 Nov 2014 12:01

What is [b,c,d,r,a]? are these variables?
Anyway, the answer is in the execution example, as you mentioned.