Hi can you guys explain why the time complexity is O(n x k ^2)?
Hello,
The time complexity is O(n x k^2) because, first, we iterate over all list of movies from each country i.e. n number of lists. In each iteration, we combine two lists by comparing every element of one list (with k elements) to every element of the other list (with k elements) which makes k^2 iterations. So the complexity for each combining iteration becomes k^2. This way the overall complexity becomes n times k^2.
I believe the time complexity is O(n x k). Let me explain.
Let’s say we have a list of n items (no conflict here).
Among the lists, we have two linked lists that have no common item, such as t1 = [1, 3, 5, 7, 9] and t2 = [2, 4, 6, 8, 10, 11]. In this case, the while loop in merge2_country will iterate 9 times. Thus, the iteration is less than (k * 2) where k is the length of the smaller list.
Let’s say we have two linked list with all conflicting items, such as t1 = [1, 2, 3, 4, 5] and t2 = [1, 2, 3, 4, 5]. In this case, the while loop will run 8 times, again it is less than (k * 2) where k is the length of the smaller list.
Thus, the time complexity is O(n x 2 x k) ~ O (n x k).
Please let me know, if there is a broken step in my thought process.
Hi @Ali_Kaya,
As we have k lists, we can assume that each list contains n elements. To merge the first two arrays, it would take n + n time, i.e., 2n. It would take 2n + n = 3n time to merge the third list. The last merge would take n * k time as we go on. The total time for all the merges would result in the following formulation:
n + 2n + 3n + … + k * n
=> n * k * (k + 1) / 2
Hence the O(n * k^2) time complexity for this feature.