Wound: Везде где ни встретишь описание алгоритмов фибоначи, во всех книжках, на всех ресурсах - везде, пишут что сложность вышеописанного алгоритма О(N), ну например вот статья: https://leetcode.com/articles/fibonacci-number/#
Так что тут как бы и думать нечего.
