Понимать сложность алгоритмов - сложно. В общем случае глядя на исходних достаточно трудно сказать какое там o(n). Особенно если есть рекурсии и предикаты которые срабатывают с вероятностью которую мы не знаем.
Вообще, нарабатывая опыт. Например обход элементов квадратной матрицы имеет квадратичную стоимость а обход куба - кубическую. Это из простого. Шаблоны дихотомического поиска почти всегда содержат в основе своей формулы логарифм по основанию 2. И комбинаторные алгоритмы (сочетания и перестановки) - практически всегда содержат в своей основе n под факториалом.
Кстати если формула содержит суперпозицию факториала и полинома - то полином можно выкинуть. Т.к. в сравнении пределов факториал улетает в бесконечность быстрее и соотв. решение зависит только от факториала.
Я не очень понимаю зачем для собеседования знать оценку неизвестных алгоримов. Я прошел не один десяток интервью и меня никогда никто не просил оценить сложность неизвестного алгоритма.
По поводу Дональда Кнута. Ничего он не поймет. Кнут писал 40 лет назад. Писал про железо которого уже не существует (ленточные накопители) и продавливал свои идеи алгоритмизации на ограниченном числе ресурсов. Кнут просто издевается над современным читателем имеющим ноутбук и смартфон тем фактом что заставляет изучать несуществующий компьютер MMIX (это такая себе машинка-калькулятор вроде Феликса или Энигмы, такие вот у меня ассоциации) и под него-же писать и читать код. Ну кому это надо!
Сегодня я снимаю шляпу перед тем трудом который он сотворил. Но если студент хочет ПРОСТО освоить тему оценок сложностей алгоритмов то можно взять что-то более быстрое и эффективное. Вирт. Седжвик. Даже Кормен.
