What is the time complexity of map and join functions in Python?

help
1

Hi Chefs,

Since 2 days I was searching for time complexity of map() and join() functions in Python, but I couldn’t find exact answer in Google.

Please some one help me on this doubt.

Thanks and regards.

2

I think we can get time complexities based on what they do.

map(function, iterable, ...) returns a list by applying function taking iterable as argument. So, time complexity is \text{len(iterable)}\cdot \text{complexity of function}. Documentation

string.join(words) joins words by inserting string between them. Complexity – \text{len(words)}\cdot \text{len(string)}. Documentation

Note that these are for python2.7
Pretty sure if you plot running time vs size of input graphs for this it will match the above.

1 Like
3 
l = list(input())
ls = []
cnt=0
for i in range(len(l)):       #O(n)
    if int(l[i])%2==0:
        cnt+=1
a=1
for i in range(len(l)):       #O(n)
    if int(l[i])%2==0:
        ls.append(str(cnt))   #O(1)
        cnt-=a
        continue
    ls.append(str(cnt))       #O(1)
print(' '.join(ls))           #O(len(ls))


#input : 574674546476
#output : 7 7 7 6 5 5 4 4 3 2 1 1

In this case the join used in print will be O(len(ls)) right!!!

4

It should be AFAIK. Can you provide a link to the problem you were trying to solve and your submission?

EDIT: I ran for i in {1..10}; do time echo $((i*1000000)) | python -c "' '.join([str(i) for i in range(input())])"; done in bash. Looks to be O(len(list))

Output

real    0m0.291s
user    0m0.267s
sys 0m0.025s

real    0m0.556s
user    0m0.491s
sys 0m0.064s

real    0m0.839s
user    0m0.767s
sys 0m0.072s

real    0m1.100s
user    0m0.964s
sys 0m0.136s

real    0m1.394s
user    0m1.274s
sys 0m0.120s

real    0m1.650s
user    0m1.466s
sys 0m0.184s

real    0m1.428s
user    0m1.762s
sys 0m0.204s

real    0m2.192s
user    0m1.968s
sys 0m0.224s

real    0m2.489s
user    0m2.243s
sys 0m0.244s

real    0m2.736s
user    0m2.435s
sys 0m0.301s
5

Hey @psaini72,

Thanks for the reply. Actually it is not from any online community, it’s just an assignment question which I have to complete and submit.

Thanks for the efforts man :blush: