Python | Dividing two lists

Sometimes we come across situations in which we require to apply a particular function to each element of two lists at a similar index. The most popular of them are 4 of the elementary mathematics operations. These are quite similar and come up as applications for certain utilities. Let’s discuss certain ways in which the division of two lists can be performed. 

Using a loop

The original list 1 is: [3, 5, 2, 6, 4]
The original list 2 is: [7, 3, 4, 1, 5]
The division list is: [0.42857142857142855, 1.6666666666666667, 0.5, 6.0, 0.8]

Time complexity: O(n), where n is the length of the lists. We iterate over each element once.
Auxiliary space: O(n), where n is the length of the lists. We create a new list to store the division results.

Using zip() + list comprehension 

The zip operation can be used to link one list with the other and the computation part can be handled by the list comprehension and hence providing a shorthand to this particular problem. 
 

The original list 1 is : [3, 5, 2, 6, 4]
The original list 2 is : [7, 3, 4, 1, 5]
The division list is : [0.42857142857142855, 1.6666666666666667, 0.5, 6.0, 0.8]

Time Complexity: O(n*n), where n is the length of the list test_list 
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list 

Using map()

Using the map function is the most elegant way in which we can possibly perform the twining of a function with both lists. Different operations other than division can also be applied to it. 

The original list 1 is : [3, 5, 2, 6, 4]
The original list 2 is : [7, 3, 4, 1, 5]
The division list is : [0.42857142857142855, 1.6666666666666667, 0.5, 6.0, 0.8]

Using recursion

One approach could be to use recursion. Here is an example of how this could be implemented:

First, it defines a function called divide_lists that takes in two lists as arguments, lst1 and lst2. It also has a base case where it returns an empty list if either of the lists is empty.

Then, it uses recursion to divide the first elements of both lists and append the result to a new list called the result. It does this by calling the divide_lists to function again with the rest of the elements in both lists, using list slicing to remove the first element from each list.

Finally, it returns the result list, which contains the element-wise division of the two lists.

[0.42857142857142855, 1.6666666666666667, 0.5, 6.0, 0.8]

This solution has a time complexity of O(n), where n is the length of the lists, since the function processes each element of the lists once. It has a space complexity of O(n) as well, since the function creates a new list of the same size as the input lists.

Using heapq

Algorithm:

1. Create an empty list res to store the result.
2. Iterate through the list1 and list2, dividing the corresponding elements in each list and appending the result to res.
3. Return the smallest N elements in res using heapq.nsmallest().

[0.42857142857142855, 0.5, 0.8, 1.6666666666666667, 6.0]

Time complexity:

The time complexity of this algorithm is O(N*log(N)) where N is the length of the input lists.
The division operation and list iteration both take O(N) time, and heapq.nsmallest() takes O(N*log(N)) time as it uses a min-heap.
Auxiliary Space:

The space complexity of this algorithm is O(N) as we are creating a list to store the result.

Using quicksort

The code takes two lists as input, sorts them using quicksort, merges them into a single list of tuples sorted by the first element, and then performs element-wise division on the merged list to produce the output.

ALGORITHM:

1.Define the quicksort function that takes an array as input and recursively sorts it using the quicksort algorithm.
2.If the length of the input array is less than or equal to 1, return the input array.
3.Select a pivot element from the input array. In this implementation, the pivot is chosen as the middle element of the array.
4.Partition the input array into three subarrays: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
5.Recursively apply the quicksort function to the subarrays less than and greater than the pivot.
6.Combine the sorted subarrays and the middle array to obtain the final sorted array.
7.Sort the two input lists by element-wise pairing them together as a list of tuples, and sorting based on the first element in each tuple.
8.Perform element-wise division on the merged list to produce the output.

[0.5, 0.42857142857142855, 0.8, 1.6666666666666667, 6.0]

Time Complexity:

The time complexity of quicksort algorithm is O(n log n) in the average and best case, and O(n^2) in the worst case. 

Auxiliary Space:

The overall space complexity of the algorithm is O(n).