educative.io

How is the time complexity O(n*(k^2))?

Courses
,
#1

In the solution, we loop through the list once inside mergeKCountries function. This makes time complexity O(k), where k is the number of lists.
Next, we go through each list in merge2Countries which is O(n), where n is the maximum length of the list.

This makes time complexity => O(n*k).

Is this the right logic?

Thanks in advance.

Type your question above this line.

Course: https://www.educative.io/collection/10370001/5808777738059776
Lesson: https://www.educative.io/collection/page/10370001/5808777738059776/5391999346147328

#2

While in merge2_country( list1, list2 )
the comparison count increases !
For example, for the first loop, you compare
list 1 with max length n
and
list 2 with max length n
=> then total comparison count is 2n here.

For the next loop, you compare
res with max length 2n
and list 2 with max length n
=> total comparison 3n

so it becomes (2n) + (3n) + … (kn) = O(k^2*n)

1 Like