5 ms·
n = 100_000 K = 2 # seconds time_secs = K * n * log(n) t = timedelta(seconds=time_secs) t # datetime.timedelta(days=26, seconds=56185, microseconds=
by akdor1154 6y ago
n = 100_000
K = 2 # seconds
time_secs = K * n * log(n)
t = timedelta(seconds=time_secs)
t # datetime.timedelta(days=26, seconds=56185, microseconds=92994)
So around a month (at 24×7, so in reality more like 3 months) of time sorting if in a horrendous abuse of big O notation we assume that sorting the notes takes 2 * n * log(n) seconds.
I guess he could use a pigeonhole sort though - at constant factor of 10 seconds this gives 11 days 49600 seconds.
- mamon 6y agoBigger problem is that there are 11.7 B one dollar bills in circulation [1]. Even having that $100k sorted you still only stand 1: 117000 chance of winning. [1] https://www.titlemax.com/discovery-center/money-finance/how-many-dollar-bill-circulated/ https://www.titlemax.com/discovery-center/money-finance/how-...
- egman_ekki 6y agoBut there is no downside (besides the time cost of the one-dollar-bill operation). If you don't win, you just put the money back to the bank. What is interesting is that you could theoretically deposit (part of) the money into your account and then withdraw somewhere else, so change the odds slightly.
- FatalLogic 6y agoThat searching is quite expensive, considering the odds (only one chance per day). Besides, there was also significant additional downside, which became obvious in this case: The risk of having a pile of cash in your house which could be stolen
- bluGill 6y agoBack when this contest was running bank savings accounts paid enough interest that there was a real loss of having all your money withdrawn. I'm not sure what year this was, so I can't look up the interest rate, but a couple thousand lost per month isn't an unreasonable estimate.
- kgwgk 6y ago20+% interest paid in a savings account (2% per month) seems unreasonable.
- bluGill 6y ago6%Apr, and a few hundred thousand.. 20% might have been possible briefly in the 1970s
- deleted 6y ago[deleted]
- jacurtis 6y ago> a couple thousand lost per month isn't an unreasonable estimate. This was the mid-to-late 80's... it wasn't THAT long ago. The majority of people reading this were alive back then. Yes interest rates were higher in the 80s and 90s, but not as high as you are insinuating. At this time (from my memory) you could expect about 1% per year in interest. Maybe upwards of 2% annual interest if you had a very generous deal with a bank, but even that is unlikely. At 1% a year, his $100,000 is generating ~$83 per month in interest. Granted he could do other things with his money to appreciate it. Which would increase his time value of money. But the opportunity cost of checking/savings account interest was pretty small. Granted the guy was stupid to begin with for even thinking he could win this contest and for putting $100k in cash in his house in case... I don't know, someone broke in or something... wait, that's what happened.
- drdec 6y agoI would humbly suggest that perhaps your memory isn't quite accurate. https://www.bankrate.com/banking/cds/historical-cd-interest-rates/ https://www.bankrate.com/banking/cds/historical-cd-interest-... https://barbarafriedbergpersonalfinance.com/savings-account-rates-1980s-1990s/ https://barbarafriedbergpersonalfinance.com/savings-account-... Also, due to inflation, if you want to compare with today's dollars you need to multiply the amounts by approximately 4.
- kgwgk 6y ago
- jacobr1 6y agoBoth loss of interest and loss of deposit insurance. You can lose the money to theft or fire.
- paxys 6y agoThe only downside is someone could break into your house and steal all the cash, but of course that would never happen.
- OscarCunningham 6y agoI'd sort into 10 piles by first digit, and then sort each pile into ten piles by second digit. This would involve looking at each note twice, so at two seconds per note it would take 400000 seconds, or around 7 days of two people working 8 hours a day. The small piles would have 1000 notes in them, which is easy to check in a day.
- genera1 6y ago> The small piles would have 1000 notes in them, which is easy to check in a day. By the time you could even buy an 8-bit home computer for couple hundred dollars, store all the serial numbers on a floppy and simply search through them once per day
- OscarCunningham 6y agoThat would let you check instantly if you had that dollar, but you'd then have difficulty physically finding it.
- llampx 6y agoCreate an index. Sort the notes into sets of 1000 and label them, add the label as a column into your Foxpro database.
- mywittyname 6y agoMost likely scenario, you never look sort through it again. Least likely scenario, you get $30,000 (probably like $280,000 in today's money) to dig through them all one more time.
- Dylan16807 6y agoThat would take so much more time than sorting each batch of 1000 notes, and sorted notes let you do your daily check in less than a minute.
- frombody 6y agoI'm sure I'm missing something in this discussion, but why wouldn't you just OCR the serial numbers and put the results in a textfile and sort that?