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

Popular posts from this blog

PHPMotion implementation - URL based videos (Hosted on separate location) -

javascript - Using Windows Media Player as video fallback for video tag -

c# - Unity IoC Lifetime per HttpRequest for UserStore -