Analyse the running time of the following divide and conquer algorithm. For the algorithm, establish a recurrence for the running time and derive a tight asymptotic bound. The input is an integer n ≥0 and the function returns a non-negative integer
Fibonacci-numbers via the definition.
`1 function fibonacci(n)
2 if n ≤1 then
3 return n
4 else
5 return (fibonacci(n −1) + fibonacci(n −2))`
chat gpt says O(1.618033^n) but I dont understand its way.
