python - Calculating the time complexity of this specific code -
im trying figure out time complexity of following code. lst_of_lsts
contains m
lists lengths @ n
.
this think: runs in o(m*n)
, minimum = o(m*n)
, remove = o(m*n)
.
overall o(m*n)*o(m*n)
= o(m^2*n^2)
am right?
def multi_merge_v1(lst_of_lsts): = [e lst in lst_of_lsts e in lst] merged = [] while != []: minimum = min(all) merged += [minimum] all.remove(minimum) return merged
def multi_merge_v1(lst_of_lsts): # m lists of n = [e lst in lst_of_lsts e in lst] # messy. enumerate n*m list items --> o(nm) merged = [] # o(1) while != []: # n*m items initially, decreases in size 1 each iteration. minimum = min(all) # o(|all|). # |all| diminishes linearly (nm) items, o(nm). # can re-use work here. should use sorted data structure or heap merged += [minimum] # o(1) amortized due table doubling all.remove(minimum) # o(|all|) return merged # o(1)
the overall complexity appears o(nm + nm*nm + 1) = o(n^2m^2+1). yikes.
Comments
Post a Comment