Бонус. Асимптотика (1-я пара, 2024/25 учебный год)

1. [22 минут] Ещё теоремы:
   1. [5 минут] Доказательство по индукции на примере T(n) = max_x=1..n-1[T(x) + T(n-x) + x(n-x)].
   2. Как догадаться до ответа?
   3. [2 минут] Примеры на экспоненциальные соотношения: числа Фибоначчи, оценки 2ⁿ и 2^n/2
   4. [15 минут] Теорема об экспоненциальных рекуррентных соотношениях T(n) = ∑_i b_i T(n-a_i). Применение к числам Фибоначчи.
   
   
2. [10 минут] Ещё примеры асимптотик
   1. T(n) = 2T(n/2) + Cn, T(n) = 2T(n/2) + O(n) (константа вынесется)
   2. T(n) = T(n-1) + n
   3. T(n) = T(n-3) + T(n-3)
   4. T(n) = T(n-1) + T(n-2) + T(n-2)
   
   
3. [15 минут] Интегралы
   1. Определение интеграла, связь с суммой
   2. Мы умеем дифференцировать! log'(x) = 1/x, (xⁿ)^' = nx^n-1
   3. Другое доказательство времени для примера со списком делителей
   
   
4. [5 минут] Ещё про асимптотики
   1. Определение O и o через пределы
   2. log^an = O(n^b) <−−- Разбирается на практике (есть две задачи во 2-м блоке)
   3. n^a = O(bⁿ) <−−- Разбирается на практике (есть две задачи во 2-м блоке)