# Is the complexity of this code quasilinear time?

Algorithm explanation: based on an unsorted list I want to find the indexes of the values in another sorted list. Note that all values are unique and the two lists have the same values, only in different order, for example:

``````# O(log n)
def binary_search(data, value):
n = len(data)
left = 0
right = n - 1
while left <= right:
middle = (left + right) / 2
if value < data[middle]:
right = middle - 1
elif value > data[middle]:
left = middle + 1
else:
return middle
raise ValueError('Value is not in the list')

# O(n log n)
def find_indexes(data1, data2):
return [binary_search(data2, value) for value in data1]

if __name__ == '__main__':
data1 = [9, 1, 8, 2]
data2 = [1, 2, 8, 9]
print(find_indexes(data1, data2))
# >> [3, 0, 2, 1]
``````

Can someone please confirm that the function `find_indexes` has quasilinear time complexity?

Note that this is not a real problem and I'm not trying to improve this algorithm. I'm just trying to exemplify how a quasilinear algorithm works in a simple way.

• Yes, this is clearly quasilinear. You're doing a `O(log n)` operation (binary search) `n` times. Mar 4, 2019 at 9:39

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if `T(n) = O(n log^k n)` for some positive constant `k`; linearithmic time is the case `k = 1`.
``````def find_indexes(data1, data2):
calls `binary_search` once for each of `n` elements in `data1`. Since `data1` and `data2` are the same size by contract, `binary_search` runs in `O(log n)` time. In total that is `n * O(log n) = O(n log n)` which is quaslinear for `k=1` (or linearithmic) as per the definition.