Квадратичне зростання

У математиці кажуть, що функція або послідовність виявляють квадратичне зростання, якщо її значення пропорційні квадрату аргументу функції або порядковому номеру члена послідовності. Часто термін «квадратичне зростання» означає загальніше «квадратичне зростання в границі», коли аргумент функції або порядковий номер члена послідовності прямує нескінченності — у нотації великого Тета, ${\displaystyle f(x)=\Theta (x^{2})}$.^[1] Це можна визначити як неперервно (для дійснозначної функції дійсної змінної), так і дискретно (для послідовності дійсних чисел, тобто дійснозначної функції цілої або натуральної змінної).

Прикладами квадратичного зростання є:

• будь-який квадратний многочлен;
• деякі послідовності цілих чисел, наприклад трикутні числа. Значення ${\displaystyle n}$-го трикутного числа ${\displaystyle n(n+1)/2}$, що приблизно дорівнює ${\displaystyle n^{2}/2}$.

Для дійснозначної функції дійсної змінної квадратичне зростання еквівалентне тому, що її друга похідна є сталою (тобто третя похідна дорівнює нулю), і, отже, функції з квадратичним зростанням є точно квадратними многочленами, оскільки вони є ядром оператора третьої похідної ${\displaystyle D^{3}}$. Подібно, для послідовності (дійснозначної функції цілої або натуральної змінної) квадратичне зростання еквівалентне тому, що друга скінченна різниця є сталою (третя скінченна різниця дорівнює нулю),^[2] і, отже, послідовність із квадратичним зростанням також є квадратним многочленом. Дійсно, цілочисельна послідовність із квадратичним зростанням є многочленом із цілими значеннями нульового, першого та другого біноміальних коефіцієнтів. Коефіцієнти можна визначити, взявши многочлен Тейлора (для неперервного) або многочлен Ньютона (для дискретного).

Приклади алгоритмів:

• Час, якого в найгіршому випадку потребують деякі алгоритми, такі як сортування включенням, як функція довжини вхідних даних.^[3]
• Кількість живих клітин у шаблонах клітинних автоматів, що заповнюють простір, наприклад, розмножувача, як функція кількості кроків моделювання.^[4]
• Закон Меткалфа, згідно з яким вартість комунікаційної мережі зростає квадратично залежно від кількості користувачів.^[5]

• Експоненційне зростання