title: Efficient algorithm for determining if a date is in DST
body: <p>I'm looking for a better than O(n) algorithm to determine if a date in the future will have daylight savings time applied (and how much).  Given a year, month, day, hour, minute and time zone (and a copy of the Olsen Time Zone database) how does one efficiently determine if that date will be in DST?  I'm looking for the algorithm, not a library function to call.</p>
  
  <p>Thank you.</p>
  
  <p>FURTHER EXPLANATION:  The date library I'm using is very slow when you create an object with a date in the future and a time zone.  It turns out its doing a linear calculation to calculate if the date is in daylight savings time.  Not only that, its doing this at object creation time.  Obviously it could wait until asked, but it should also be more efficient.</p>
  
  <p>Sure, DST rules change and a date library can't predict the future, but the alternative is to put an arbitrary upper limit on localized dates.</p>