What is time complexity of the code?

Question

 def multi_merge_v1(lst_of_lsts):
      all = [e for lst in lst_of_lsts for e in lst]
      merged = []
      while all != []:
            minimum = min(all)
            merged += [minimum]
            all.remove(minimum)
      return merged

What is the time complexity of this code? is it O(2mn)? Because creating "all" requires mn steps and also while requires mn steps

you could use heapq.merge(*lst_of_lsts), here's a code example that uses merge() to sort a text file that doesn't fit in memory — jfs
– jfs, Commented Mar 29, 2014 at 12:35
This question appears to be off-topic because it is about algorithm complexity, not programming. Try Computer Science instead. — Martijn Pieters
– Martijn Pieters, Commented Mar 29, 2014 at 15:39
@MartijnPieters: Why would you want to delete the answered question? There is no migration to cs.stackexchange as I understand. And even if the migration were possible, you should avoid migrating answered questions and don't migrate for the sake of migration. — jfs
– jfs, Commented Mar 30, 2014 at 14:07
@J.F.Sebastian: There is no automatic migration path; and I did not intent for anything to be deleted, but fair enough. The barrage of questions by this user were mostly off-topic still though. — Martijn Pieters
– Martijn Pieters, Commented Mar 30, 2014 at 14:41
@MartijnPieters: As far as I remember, most closed questions are deleted automatically after some time. Previous questions shouldn't matter unless it is a duplicate. — jfs
– jfs, Commented Mar 30, 2014 at 14:55

jfs · Accepted Answer · 2014-03-29 12:26:13Z

1

It is O((m*n)**2) because while loop is executed m*n times and min(all), all.remove(minimum) are O(n*m) operations.

answered Mar 29, 2014 at 12:26

jfs

417k210 gold badges1k silver badges1.7k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user7777777 Over a year ago

what about creating "all" isn't it mn?

jfs Over a year ago

@user7777777: O(n**2 + n) == O(n**2) i.e., mn doesn't matter compared to (mn)**2

user7777777 Over a year ago

Doesn't "all" is a list that doesn't have lists in it instead a one long list created of lists that were in lst_of_lsts, so why min(all) doesn't requires m+n operations? =

jfs Over a year ago

@user7777777: len(all) is m*n assuming len(lst_of_lsts) == n and len(sublist) == m Look at the nested loop in the list comprehension for e in lst is executed for every list

Collectives™ on Stack Overflow

What is time complexity of the code?

1 Answer 1

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Linked

Related