1
 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

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
user7777777
  • 219
  • 2
  • 10
  • you could use [`heapq.merge(*lst_of_lsts)`](http://docs.python.org/3.5/library/heapq.html#heapq.merge), here's a [code example that uses `merge()` to sort a text file that doesn't fit in memory](http://stackoverflow.com/a/16954837/4279) – jfs Mar 29 '14 at 12:35
  • This question appears to be off-topic because it is about algorithm complexity, not programming. Try [Computer Science](http://cs.stackexchange.com/help/on-topic) instead. – Martijn Pieters Mar 29 '14 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](http://meta.stackexchange.com/q/10249/137096). – jfs Mar 30 '14 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 Mar 30 '14 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 Mar 30 '14 at 14:55
  • @J.F.Sebastian: No, they are only deleted if unanswered, and with a score of 0 or less. See the [FAQ](http://meta.stackexchange.com/questions/5221/how-does-deleting-work-what-can-cause-a-post-to-be-deleted-and-what-does-that). – Martijn Pieters Mar 30 '14 at 14:58
  • @MartijnPieters: Thank you for the link (a [quick search](http://meta.stackoverflow.com/search?q=when+closed+question+are+deleted) does not yield it). Questions with answers *were/are/will be* deleted automatically with some exceptions even according to the set of rules enumerated in [the link](http://meta.stackexchange.com/a/5222/137096). – jfs Mar 30 '14 at 18:29
  • The majority of rules exempt questions with answers. The only way your answer is at jeopardy is if the question had a negative vote and the question asker account was deleted. – Martijn Pieters Mar 30 '14 at 18:51
  • @MartijnPieters: related: [When/Why a question with accepted answer and more answers is deleted?](http://meta.stackoverflow.com/q/270586/4279) – jfs Sep 04 '14 at 16:28
  • @J.F.Sebastian: than only applies when the author of the question is deleted. That is an exception to the rule. – Martijn Pieters Sep 04 '14 at 16:29

1 Answers1

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.

jfs
  • 399,953
  • 195
  • 994
  • 1,670
  • what about creating "all" isn't it mn? – user7777777 Mar 29 '14 at 12:40
  • @user7777777: `O(n**2 + n) == O(n**2)` i.e., `mn` doesn't matter compared to `(mn)**2` – jfs Mar 29 '14 at 12:42
  • 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? = – user7777777 Mar 29 '14 at 12:52
  • @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 – jfs Mar 29 '14 at 13:28