Lily pads
A patch of lily pads on a lake doubles in size every day. It covers the whole lake on day 48. On what day did it cover half the lake?
Show hint
Work backwards one day.
Show solution
Day 47. It doubles every day, so the day before it was full, it was half full.
Doubling is how exponential growth behaves: almost nothing seems to happen for a long time, then everything happens at once. An O(2n) algorithm feels the same way: fine for n = 20, hopeless for n = 60.
Want a problem like this every day? See today's problem and keep a streak going.