Как научиться определять алгоритмическую сложность "на глазок"?

Когда речь идёт о более-менее простых алгоритмах, всё и так довольно очевидно - например, какой-то алгоритм вызывается в цикле, число итераций которого не превосходит n, то итоговая асимптотика выйдет O(n*k), где k - время выполнения алгоритма.

Менее тривиальными являются рекурсивные алгоритмы, а также такие, для оценки сложности которых нужен амортизационный анализ. Для рекурсивных алгоритмов есть основная теорема, а также, например, теорема Акра-Баззи, но они не очень интуитивны и не очень часто встречаются на практике. 

Можно их оценивать через дерево рекурсии - создаёте дерево рекурсивных вызовов, в вершинах которого записываете величину, равную числу действий, которые будут сделаны в этом запуске, не включая рекурсивных. Далее нужно просуммировать эту величину по всем вершинам. Часто на одной высоте в вершинах записано одно и то же обозначение, поэтому суммируется на самом деле некий ряд, оценить асимптотику которого уже обычно не так сложно.

Амортизационный анализ нужен в тех случаях, когда алгоритм на любом отдельном шаге может работать долго, но его суммарное время работы гарантированно окажется лучше, чем худшее время работы на одном шаге, умноженное на число шагов. Он часто делается через потенциалы - мы вводим какую-то величину, которая за одно действие не может сильно измениться и на основании её изменения за весь алгоритм, можем сделать вывод о числе действий. 

Например, рассмотрим алгоритм двух указателей - изначально два указателя находятся на первом элементе массива. Далее второй монотонно пробегает все элементы, а первый его догоняет, делая неопределённое число шагов на каждой итерации. Возьмём в качестве потенциала разность между указателями. В начале она равна 0, а в конце не превышает n. При этом на каждом шаге она может либо увеличиться на 1, если первый указатель не сдвинулся с места, либо сократиться на неопределенное число. Но каждому сокращению должно предшествовать увеличение, так как это расстояние - неотрицательная функция. Увеличения может быть не больше n, значит, суммарное число сокращений также не превосходит n и общая асимптотика выйдет O(n).

Это всё совсем базовые приёмы, более глубокое понимание же должно прийти с практикой. Ну и, конечно, стоит просто изучить много алгоритмов, знать и понимать, как доказывается асимптотика для них.