Резкое увеличение времени, при list.add(0, new Object()); для LinkedList

Итак, ситуация такая: я решал задачу, которая возвращает время в милисекундах, требующееся для заполнения коллекции типа LinkedList (в нулевой сегмент). Кстати, да, это на порядок быстрее происходит, чем для ArrayList, но речь идет не об этом.

Я стал исследовать, как меняется время работы программы, например, для 1000 элементов, для 10000 элементов, итд.
public static void main(String[] args) { System.out.println(getTimeMsOfInsert(new LinkedList())); } public static long getTimeMsOfInsert(List list) { long currentTime = new Date().getTime(); insert10000( list ); return new Date().getTime() - currentTime; } public static void insert10000(List list) { for (long i=0;i<10000000;i++) { list.add(0, new Object()); } } И получил такой результат 10^4 элементов работал 2 ms 10^5 элементов работал 15ms 10^6 элементов работал 187ms 10^7 элементов работал 2,327 секунд И теперь, внимание - я ожидал, что для 10^8 элементов алгоритм будет работать примерно 20 секунд... однако на деле: 10^8 элементов работал 202,215 секунд Дополнительная информация: процессор core i7 4810MQ (2,8 GHz) 6 MB кэш памяти 32 GB оперативной памяти Win8 64 Во время выполнения программы с 10^8 элементами я запустил диспетчер задач - процессор пахал на 100%, несколько сотен Мегабайт оперативной памяти заполнялись. Вопросы: 1 - почему при переходе от 10^7 к 10^8 элементам алгоритм увеличивает время работы не на 1, а на 2 порядка? Моя гипотеза такова: закончился кэш процессора и массив пошел в оперативную память. Но неужели в моем распоряжении несколько МБ кэша процессора, при условии, что помимо IDEA ничего не запущено? 2 - есть ли возможность сократить время работы алгоритма до примерно 20 секунд? 3 - сколько примерно будет программа вычислять 10^9 элементов?