Description

Homework 2 Alex McLeod
Merge k Sorted Lists

Above is an algorithm written in python that merges k lists using a heap. The code runs in
O(nlogk) time, where n is the total number of items in k_lists, and where k is the number of lists.
We can see that pushing to the heap takes O(nlogk) operations, as it takes O(logk) operations to push to the heap, over n iterations. Popping from the heap and appending to a new list only takes O(n) operations.
Run-time analysis
Device Specs/Language Language:

Computer:

CPU:

Memory:

Algorithm Comparison Table:
Average run time of both algorithms
Size of list brute force binary search
10 9.68E-05 0.00019968
100 0.0005943 0.00029833
1000 0.0024897 0.0009975
10000 0.5319317 0.01485856
100000 0.1558083 0.03059528
1000000 2.7116085 0.492155
Note: All the values in the brute force and binary search columns are in seconds.

Note: Both axes are logarithmic
Conclusion
From the results above, it is clear that for large data sets, the binary search method is
faster, by over 5 times in some trial runs! This is because the brute force method runs in O(𝑛2) time, while the binary search method runs in only O(nlogn) time. Choice of algorithm matters because by choosing a faster algorithm, we can save tremendous amounts of computing power and time, as was shown in this assignment.
Code
Attached in the homework submission is the python file that contains my code.