Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
March 6th, 2002, 03:54 PM
 estrabd
o0o.o0o

Join Date: Feb 2001
Location: m00n
Posts: 194
Time spent in forums: 2 h 15 m 59 sec
Reputation Power: 101
less complex (as in big-O) date algorithm?

I wrote a script in bash that takes in the argument YEAR, MONTH, DAY, "+" or "-", NUM_DAYS that either adds or subtracts the NUM_DAYS to/from the date provided and returns the date that is NUM_DAYS +/- the initial date.

My question: is there an algorithm that can determine this in one operation? Right now, it cycles through the dates linearly based on NUM_DAYS, so I guess is it O(n). I am looking for one that is less, maybe O(1) or O(n log n).

Thanks,
Brett

#2
March 8th, 2002, 03:22 AM
 WoR
Registered User

Join Date: Mar 2002
Posts: 20
Time spent in forums: < 1 sec
Reputation Power: 0
If you first determin, if the number of days will overflow yxour current month, the see if the rest will overflow the current year, then check how many years fit in, then (back down again) if the rest is greater than a year , then see if the rest is enought for a month ect. you can make it run in O(1)-operations at somewhat enhanced complexity.

You have to check how long a year/month is depending on the first date.
Checks (in worst case) have to be done:
one for the current year.
one for the n-years inbetween
one for the last year
one for the current month
one for the months to next year
one for the months in hte last year
Actually the complexity rises at O(log(days)) up to the region of 400 years the stays constant (if you don't include calender changes in history) afterwards.

Hope this helps to keep you busy implementing for some time

#3
March 13th, 2002, 09:42 PM
 The Ostrich
Contributing User

Join Date: Mar 2002
Location: Oxford, UK
Posts: 28
Time spent in forums: < 1 sec
Reputation Power: 0
Just to be pedantic

O(n log n) is worse than O(n)

#4
March 20th, 2002, 07:07 AM
 martinus
Junior Member

Join Date: Mar 2002
Posts: 6
Time spent in forums: < 1 sec
Reputation Power: 0
do it this way

Last edited by martinus : March 20th, 2002 at 07:10 AM.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > less complex (as in big-O) date algorithm?