A long distance runner wants to carry only a single water bottle along the route and she can run k miles on one bottle of water. Before the race, she is given a map of all n watering stops (i.e. mile markers of these stops). Design an efficient algorithm for determining where she should take a new bottle in order to make as few stops as possible. Estimate its time complexity.