Асимптотика (4 сентября 2020)
----------------------------

0. Оргвопросы

1. Общие мысли про желание мерить время работы
1.1 2.3GHZ для C++, 1e6 ops/sec для Py, считаем max n, что n^2 влезет в секунду.

1. Big O
1.1 Определение O, Omega, Theta, серия примеров.
1.2 Определение o, w, серия примеров
1.3 Свойства (симметричности, транзитивности, etc).
1.4 Примеры с O
1.4.1 Гармонический ряд, "анонимная функция"
1.4.2 (?) Формула стирлинга
1.4.3 f = O(Theta(O(g))), f = Omega(w(Theta(g))), f = Theta(o(Theta(O(g))))
1.4.4 log_2(n) = Theta(log_5(n))

2. Ещё свойства и примеры
2.1 f +- o(f) = Theta(f)
2.2 f = poly(n) => f = Theta(n^{deg f})
2.3 Пример про вложенные for, Theta(n^k), ~n^k / k!
2.4 Пример про x^2 + y^2 = N, с двумя указателями
2.5 пример про список делителей (снова гармонический ряд)

3. Мастер Теорема

4. Теорема об экспоненциальных рекуррентных соотношениях
4.1 естественные примеры: T(n) = T(n-1) + T(n-1), T(n) = T(n-1) + T(n-2)

5. Умножение многочленов и чисел
5.1 сведение чисел к многочленам
5.2 Карацуба

6. Формулировки:
6.1 log^a (n) = o(n^k) [log(n) = o(n^{0.01})]
6.2 n^a = o(c^n)  [n^5 = o(1.001^n)]