If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.


We want to swap array elements so that in the end, A[1] = 1, A[2] = 2, ..., A[n] = n. There are at most n items in the wrong place. Every swap exchanges two elements that are both in the wrong place, and moves at least one into the correct place. After n swaps all elements are in the right place, and at this point there will be no further swaps. Therefore ...

Only top voted, non community-wiki answers of a minimum length are eligible