Рекуррента за O(log n) через матрицу перехода
Как вычислить ту же трёхчленную рекурренту для большого n быстрее, чем за O(n)?
Ответьте как на собеседовании
Ответьте вслух или запишите короткие тезисы. Поле необязательно — разбор откроется после попытки.