Например, программа, которую вы написали, делает полезную работу в течение 10 мс, но на запуск и завершение виртуальный машины Ява уйдет дополнительно 5 секунд, и эти 5 секунд будут оверхедом.
Ах да, иногда от оверхеда можно избавиться. Например, в данном случае можно держать программу постоянно запущенной и готовой к выполнению задачи и тем самым избавиться от оверхеда на запуск программы.
Это где оно deprecated? Ссылку на официальный источник можно? Другое дело, что Vector — thread-safe, а значит более медленный, чем List (хотя, опять же, смотря какой List и смотря при каком сценарии использования). Но если есть обдуманная потребность в потоко-безопасности, а CopyOnWriteArrayList и synchronizedList по каким-либо причинам не подходят — Vector вполне корректно использовать.
