I Calculated the Time Complexity for this particular code as O(m * k + n) ~ O(m+n) — Is My Analysis Correct? /u/Nyctophilic_enigma Python Education

In this question if I consider the length of the array words1 as n and words2 as m, then for my first loop the time complexity would be m*k [where k is the average length of the string in words2], and for the second nested loop, n*26 [as the keys in the hashmap can not be greater than 26]. The total time complexity would be O(n+(m*k)) and roughly O(n+m). I want to clarify if I am calculating the time complexity right?

def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: ans = [] hmap = {} for i in words2: for j in i: if j in hmap.keys(): hmap[j] = max(hmap[j], i.count(j)) else: hmap[j] = i.count(j) for j in words1: flag = True for k in hmap.keys(): if hmap[k] > j.count(k): flag = False break if flag: ans.append(j) return ans 

submitted by /u/Nyctophilic_enigma
[link] [comments]

​r/learnpython In this question if I consider the length of the array words1 as n and words2 as m, then for my first loop the time complexity would be m*k [where k is the average length of the string in words2], and for the second nested loop, n*26 [as the keys in the hashmap can not be greater than 26]. The total time complexity would be O(n+(m*k)) and roughly O(n+m). I want to clarify if I am calculating the time complexity right? def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: ans = [] hmap = {} for i in words2: for j in i: if j in hmap.keys(): hmap[j] = max(hmap[j], i.count(j)) else: hmap[j] = i.count(j) for j in words1: flag = True for k in hmap.keys(): if hmap[k] > j.count(k): flag = False break if flag: ans.append(j) return ans submitted by /u/Nyctophilic_enigma [link] [comments] 

In this question if I consider the length of the array words1 as n and words2 as m, then for my first loop the time complexity would be m*k [where k is the average length of the string in words2], and for the second nested loop, n*26 [as the keys in the hashmap can not be greater than 26]. The total time complexity would be O(n+(m*k)) and roughly O(n+m). I want to clarify if I am calculating the time complexity right?

def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]: ans = [] hmap = {} for i in words2: for j in i: if j in hmap.keys(): hmap[j] = max(hmap[j], i.count(j)) else: hmap[j] = i.count(j) for j in words1: flag = True for k in hmap.keys(): if hmap[k] > j.count(k): flag = False break if flag: ans.append(j) return ans 

submitted by /u/Nyctophilic_enigma
[link] [comments] 

Leave a Reply

Your email address will not be published. Required fields are marked *