title: Advanced: How to optimize my complex O(n²) algorithm
body: <p>I have people and places data as:</p>
  
  <ul>
  <li><code>Person</code> entity has
  <ul>
  <li><code>IList&lt;DateRangePlaces&gt;</code> each having
  <ul>
  <li><code>IList&lt;Place&gt;</code> of possible places  </li>
  </ul></li>
  <li><code>Schedule</code> day pattern as ie. 10 days available 4 unavailable</li>
  </ul></li>
  </ul>
  
  <p>Within a particular <code>DateRangePlaces</code> date range one has to obey to <code>Schedule</code> pattern whether person can go to a particular place or not.</p>
  
  <ul>
  <li><code>Place</code> entity has
  <ul>
  <li><code>IList&lt;DateRangeTiming&gt;</code> each defining opening/closing times within each date range</li>
  </ul></li>
  </ul>
  
  <p>Overlapping date ranges work as LIFO. So for each day that has already been defined previously new timing definition takes preference.</p>
  
  <h2>The problem</h2>
  
  <p>Now I need to do something like this (in pseudo code):</p>
  
  <pre><code>for each Place
  {
      for each Day between minimum and maximum date in IList&lt;DateRangeTiming&gt;
      {
          get a set of People applicable for Place and on Day
      }
  }
  </code></pre>
  
  <p>This means that number of steps to execute my task is approx.:</p>
  
  <blockquote>
    <p>&sum;<sub>(places)</sub>( &sum;<sub>(days)</sub> × &sum;<sub>(people)</sub> )</p>
  </blockquote>
  
  <p>This to my understanding is</p>
  
  <blockquote>
    <p>O(x × y<sub>x</sub> × z)</p>
  </blockquote>
  
  <p><strike>
  and likely approximates to this algorithm complexity:</p>
  
  <blockquote>
    <p><strong>O(n<sup>3</sup>)</strong>
    </strike></p>
  </blockquote>
  
  <p>I'm not an expert in theory so you can freely correct my assumptions. What is true is that this kind of complexity is definitely not acceptable especially given the fact that I will be operating over long date ranges with many places and people.</p>
  
  <p>From the formula approximation we can see that people set would be iterated lots of times. Hence I would like to optimize at least this part. To ease things a bit I changed</p>
  
  <pre><code>Person.IList&lt;DateRangePlaces&gt;.IList&lt;Place&gt;
  </code></pre>
  
  <p>to</p>
  
  <pre><code>Person.IList&lt;DateRangePlaces&gt;.IDictionary&lt;int, Place&gt;
  </code></pre>
  
  <p>which would give me a faster result whether a person can go to some place on particular date, because I would only check whether <code>Place.Id</code> is present in the dictionary versus <code>IList.Where()</code> LINQ clause that would have to scan the whole list each and every time.</p>
  
  <h2>Question</h2>
  
  <ol>
  <li><p>Can you suggest any additional optimizations I could implement into my algorithm to make it faster or even make it less complex in terms of the big O notation?</p></li>
  <li><p>Which memory structure types would you use where and why (lists, dictionaries, stacks, queues...) to improve performance?</p></li>
  </ol>
  
  <h2>Addendum: The whole problem is even more complex</h2>
  
  <p>There're also additional complexities that I didn't mention since I wanted to simplify my question to make it more clear. So. There's also:</p>
  
  <pre><code>Place.IList&lt;Permission&gt;
  Person.IList&lt;DateRangePermission&gt;
  </code></pre>
  
  <p>So places require particular permissions and people have a limited time permission grants that expire.</p>
  
  <p>Additional to that, there's also</p>
  
  <pre><code>Person.IList&lt;DateRangeTimingRestriction&gt;
  </code></pre>
  
  <p>which tells only particular times that person can go somewhere during particular date range. And</p>
  
  <pre><code>Person.IList&lt;DateRangePlacePriorities&gt;
  </code></pre>
  
  <p>Which defines place prioritization for a particular date range.</p>
  
  <p>And during this process of getting applicable people I also have to calculate certain factor per every person per every place that's related to the:</p>
  
  <ul>
  <li>number of places that a person can visit on particular day</li>
  <li>person's place priority factor on that particular day</li>
  </ul>
  
  <p>All these are the reasons why I decided to rather manipulate this data in memory than using a very complex stored procedure that would also be doing multiple table scans to get factors per person and place and day.</p>
  
  <p>I think such stored procedure would be way to complex to handle and maintain. So I rather get all the data first (put it appropriate memory structures to aid performance) and then mangle with it in memory.</p>