A few weeks or so, for the first stretches of road. Self-driving cars can be useful even if limited to limited stretches of road (for example, many people would pay for the ability to read a book or play a video game in the 30 minutes they spend on the highway to work, even if that initially were the only stretch of road where their car were autonomous), and such roads could be made off limits to older cars.

And cost? Not that large, compared to the cost of building roads.