http://qs321.pair.com?node_id=931327


in reply to Re: Iterating through Two Arrays. Is there a better use of memory?
in thread Iterating through Two Arrays. Is there a better use of memory?

Nitpick: O(m+n) where m>n is just O(m). The point is, the operation is of linear order in the larger number of items.
Also, this is computationally O(1), but the original post asks for memory usage, not computation. I'm not a high enough level monk to know what the memory usage of arrays vs. hashes is, but I would hazard a guess that unless you're using an embedded environment or something else with very little available memory, that at 10k items you don't need to care too much about that.

Ben
My mission: To boldy split infinitives that have never been split before!

Replies are listed 'Best First'.
Re^3: Iterating through Two Arrays. Is there a better use of memory?
by Jeri (Scribe) on Oct 13, 2011 at 17:13 UTC

    So, you're saying. If I do just at AR suggested, I will have a linear growth rate instead of an exponential?

      Almost definitely. The worst case scenario with hashes is if every hashed key collides. In that case, you may as well be using an array.

      That's exactly what I'm saying. Your first algorithm has quadratic growth (not exponential). The second algorithm has linear growth. It's a linear cost in the smaller array to load up the hash and then a linear cost in the larger array to do all the look-ups.

      By the way: exponential growth would be O(n^m). Your original algorithm is polynomial, or quadratic to be precise O(n^2).

      Ben
      ----
      My mission: To boldy split infinitives that have never been split before!
        Note that it's only the runtime that's quadratic (or, to be precise, O(n*m)). The memory usage of the algorithm is bounded by O(n+m).
Re^3: Iterating through Two Arrays. Is there a better use of memory?
by Jeri (Scribe) on Oct 13, 2011 at 17:26 UTC

    Thank you. Hopefully, this spring I will take some more comp. math so I can become a somewhat better at growth estimates.