From: Matthew Kerwin <lists@...>
Date: 2013-03-19T19:18:12+09:00
Subject: Re: Algorithmic complexity

Rotar D. wrote in post #1102245:
> Hi,
> Can anyone tell algorithmic complexity for this operation:
>
> v.attributes.map{ |k, val| {k => info.instance_values[k]}
> }.reduce(:merge).each_pair{ |key, value|
> v.send( (key + '=').to_sym, value) }

At a glance, probably O(n)

v.attributes. # maybe O(1), probably O(n)
  map{|k,val| {k => info.instance_values[k]}}. # ??
  reduce(:merge). # O(n)
  each_pair{|key,value| v.send((key + '=').to_sym, value)} # probably
O(n)

Each of #map, #reduce, and #each_pair are straight forward linear
iterations, so should run in O(n).

The part I'm least sure about is `info.instance_values`.  I'm having to
look up the Rails doc to see what this is all about, but I assume it's
essentially an #each loop.  Then assuming the hash lookup is somewhere
between O(1) and O(n), I guess the ?? line runs in about map*(each+hash)
= O(n*m), which is just a bigger O(n).

Can anyone do a better analysis?

-- 
Posted via http://www.ruby-forum.com/.