# Big O notation

1. [Link](https://youtu.be/ZRdOb4yR0kk)
2. n / n\*log(n) / n^2 / 2^n
3. Бинарный поиск - поиск отсортированного списка отсечением половины значений на каждой итерации, сложность=log(2, n)
4. Коэфициенты в O(n) игнорируются, соотв. сортировка выбором это O(n x n)
5. Константы отбрасываются
6. O(log N) в случае, если на каждой итарации берем половину элементов
7. L \* log L - сортировка строки и еще домножить на N в случае с сортировкой массива строк
8. O(A + B) - в случае 2-х разных цыклов
9. O(A \* B) - если цикл в цикле
10. &#x20; <img src="https://4251836425-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lnd5skvXnyJUQsGuNMc%2F-LzFibtSzJizmqg8C3L6%2F-LzFkrrtvX8GMwpx6EGa%2Fimage.png?alt=media&#x26;token=f339bd1a-2e39-43e1-b77f-04c007658844" alt="" data-size="original">
11. 1. Big O - Это максимальное время выполнения, макс сложность
    2. Theta, Omega notations - среднее и минимальная сложность
