Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ratio for a deterministic (and non- deterministic) algorithms:
Let's say that renting costs 1 dollar a day and buying costs 10 dollars.
- Buy the skis on the day before, this means that you can decide to buy the skis and never use them even once: So if you decide on an algorithm that rents for 9 days and buys the skis on the 9th day, skiing for exactly 9 days (which is the worst-case input for that algorithm) would cost (9 + 10)/9 = 2.111...
- Buying the skis on the current day: So you wake up on the morning of day N, you know already you can ski - and then decide if you want to buy or rent. This changes the competitive ratio of the algorithm in the worst case (for the input: skiing for exactly 9 days) to be: (9+10) / 10 = 1.9
The second method was presented in the Wikipedia article as well as in Algorithm Design and Application by Michael T. Goodrich and Roberto Tamassia. However -it is never written explicitly when does the buying of the skis occur.
My question here is - Are these 2 problems completely different from each other? and the first one can never have a competitive ratio of 2 or less ?