0

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.

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

Given that quasilinear time means the following:

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.

it is clear that your algorithm runs in quasilinear time. The reason is because this function:

def find_indexes(data1, data2):
    return [binary_search(data2, value) for value in data1]

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.