Для простых, просто сделайте «разумную» догадку.
Для более сложных задач я бы использовал дерево повторений & mdash; мне кажется, это самый простой «алгоритм» для генерации догадки. Обратите внимание, что может быть трудно использовать дерево повторения, чтобы доказать границу (детали трудно понять правильно). Деревья повторения очень полезны для формирования догадок, которые затем подтверждаются подстановкой.
Я не уверен, почему вы говорите, что формулы не будут совпадать с выводом в Big-O или Theta. Как правило, они не совпадают точно, но это является частью сути Big-O. Частью хитрости возврата к замене является знание того, как подключить решение Big-O, чтобы заставить алгебру замены работать. IIRC, CLRS делает пример или два из этого.