Блочной аллокации у него точно нет, про это я читал какие-то их технические статьи, когда нарвался на проблему с дефрагментацией RAM. Мы из-за этого переходили на 64-битную архитектуру, потому что MathWorks нам сказал, что в 32-битной (не помню, у них ли, или у Windows) нет дефрагментации, а в 64-битной есть. А у нас регулярно вылетало out of memory при попытке аллокации матрицы на 200 МБ, например, при свободных (и доступных MatLab) 600 МБ. И проблема зачастую решалась перезагрузкой, после которой память дефрагментировалась автоматически.
Вот в этот момент они чётко рассказали, что каждая матрица у них должна занимать последовательные ячейки памяти.

А про масштаб 1:15 - да, я как-то не задумывался о его вменяемости. Но в примере по ссылке выше у MathWorks примерно такой же результат.

Квадратичный - потому что, если ты переаллокируешь каждые X строчек, и каждый раз копируешь уже накопленные данные, то операция копирования (я предполагаю, что именно она занимает время) будет рости квадратично с размером матрицы. Грубо говоря, ты копируешь 1 строку, потом 2, потом 3 и т.д., а сума арифметической прогрессии - это квадрат. А если аллокация каждые 2^n строчек (как предположил ты), то сумма степенного ряда даст 2^(n+1). То есть, линейный рост с ростом изначальной матрицы.