Algorithmic complexity of map

Question

Could you tell me the algorithmic complexity of this code, in particular, what the complexity of the function map

numero = map(lambda x: x[0], lista)
map(lambda x: (numero.count(x)), sorted(set(numero)))

Answer 1

Initially a map is O(n) because internally it iterates over the list, a linear operation, and also creates a new list of the same size to receive the transformations, also a linear operation, so we have O(n * 2) which in big O is considered O(n). However as stated in the @Jjoao comment the final complexity will vary according to the function that performs the transformation of the list (the lambdas in the case of its code), then for example if the function/lambda used to perform a constant operation the complexity would remain O(n).

As for the two lines:

1. The first is O(n) because it is made a map about lista, an O(n)), and the lambda performs only constant operation x[0];
2. The second is reasonably more complicated to evaluate. We begin by noting that sorted(set(numero))) has complexity O(n + (n log n)) (n for operation set and "n log n" for operation sorted), however "n log n" predominates over "n" so we consider the two operations only as O(n log n). Now the interesting thing is that we took this list generated by sorted(set(numero)) and feed the map with it, and for each element of this list the numero.count(x). For this part we will say that the list generated by sorted(set(numero))) has a size z and that the list numero has a size w, so we can say the map performs z times the operation numero.count, then we end up with the complexity O(z * w + (n log n)), where z * w dominates being then in reality O(z * w), Ufa!

Answer 2

Map is a part of functional programming that can be done in Python. In it we can apply the regression algorithm in smaller code space.

In this case, on its first line, the first map takes the Dice 0 from the list variable:

number = map(lambda x: x[0], list)

In the second line of your code, you are replicating the function contained in the number variable and counting the number of times that the list item[0] occurs, only the second map is being applied in the value: Sorted(set(number))

map(lambda x: (numero.Count(x)), Sorted(set(numero)))