See these codes the Fibonacci code has TC of O(2^n) while the Sum of the array has it O(n) I am getting confused due to it please help.
Fibonacci
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
Sum of the array
int go(int[] a, int l, int r) {
if (l == r)
return a[l];
int mid = (l + r) / 2;
return go(a, l, mid) + go(a, mid + 1, r);
}
int[] a = {...};
int N = a.length;
int sum = go(a, 0, N - 1);