why is my brute force(O((n1+n2)log(n1+n2))) solution faster than the optimised solution(O(n1+n2))?

user_15011824 0
Viewed 89

I was working on merging 2 sorted array of lengths n1 and n2 to return a sorted array of length n1+n2.

My brute force solution is supposed to have Time complexity of O((n1+n2)log(n1+n2)) and my optimized solution is supposed to have time complexity of O(n1+n2). Can someone please explain me how my brute force is almost 10X faster than the optimized solution. Please find the code below:

from time import time
import random

array1 = sorted([random.randint(1, 500) for i in range(100000)])
array2 = sorted([random.randint(1, 1000000) for i in range(100000)])

def brute_force(arr1, arr2):
    '''
    Brute force solution O((n1+n2)log(n1+n2)),  Space complexity O(1)

    '''
    #sorted function has the time complexity on nlog(n)
    return sorted(arr1+arr2)


def optimized_soln(arr1, arr2):
    '''
    More optimized soltuion Time Complexity O(n1+n2),  Space complexity O(n1+n2) 

    '''
    i = 0
    j = 0
    merged_array = []
    s1 = time()
    #if one of the arrays is empty , no need to merge
    if len(arr1) == 0:
        return arr2

    if len(arr2) ==0:
        return arr1

    while i<len(arr1):
        if arr1[i] <= arr2[j]:
            if i < (len(arr1) - 1):
                merged_array.append(arr1[i])
                i = i + 1
            else:
                merged_array.append(arr1[i])
                merged_array = merged_array + arr2[j:]
                i = len(arr1)
        else:
            if j < (len(arr2) - 1):
                merged_array.append(arr2[j])
                j = j + 1
            else:
                merged_array.append(arr2[j])
                merged_array = merged_array + arr1[i:]
                i = len(arr1)

    return merged_array


s1 = time()
print('Brute Force: O((n1+n2)log(n1+n2)),  Space complexity O(1)')
brute_force(array1,array2)
print('Time Taken: ',(time()-s1))
s2 = time()
print('Optimized Soln: Time Complexity O(n1+n2),  Space complexity O(n1+n2)')
optimized_soln(array1,array2)
print('Time Taken: ',(time()-s2))
data-structures time-complexity python-3.x sorting algorithm
2 Answers

Your brute force solution runs in linear time in Python. The time complexity of sort is O(n log n) in general, but that doesn't preclude it being faster in some cases. Python uses timsort, which is designed to take advantage of already sorted runs in the input data.

From https://en.wikipedia.org/wiki/Timsort

Timsort was designed to take advantage of runs of consecutive ordered elements that already exist in most real-world data, natural runs. It iterates over the data collecting elements into runs and simultaneously putting those runs in a stack. Whenever the runs on the top of the stack match a merge criterion, they are merged.

So when you append two sorted lists and then sort them using timsort, it'll find the two ranges, merge them, and then stop. Given the complexities are both linear, the speedup is simply the fact that sort is written in optimized C which can easily be 10 times or more faster than code written directly in python.

user_14007930

Each operation in Python has some overhead associated with it. Your brute force solution has O(1) such operations, while the sorting itself is implemented in lower-level code.

Optimized solution has O(n) Python operations, so the overhead is much larger in this case. So the benefit of having better algorithmic complexity in the latter case is suppressed by the overhead.

user_5021440
Related