I understand both algorithms, however the time complexity feels weird for me.
If you looked at both trees generated by both algorithms you will see that they are exactly the same, We keep dividing the tree to two halves until we reach to the end.
So why is one algorithm has complexity of 2^N while the other is nlog(n) ?
O(2^log(n)) is essentially the same as O(n). In your question you mention 2^n. You probably want to fix the title for this question. I'm not sure what you mean by tree generated by Fibonacci series. A Fibonacci tree has 4 pointers per node, but I don't think this is what you are asking about.
A naive recursive Fibonacci calculation is 2^n because it duplicates calculations, calculating F(n-1) which in turn calculates F(n-2), then it calculates F(n-2) a second time.
For an array size that is a power of 2, at the deepest level of recursion, there will be n instances of sub-arrays of size 1 produce. Then at the next deepest level, n/2 instances of merging pairs of runs of size 1 taking O(n) total time. The next level up is n/4 instances merging pairs of runs of size 2, also taking O(n) total time. So the total time complexity is O(n log2(n)).
