Determine the space complexity of the iterative and recursive Fibonacci number f

Question

Determine the space complexity of the iterative and recursive Fibonacci number function.

Here are my code, can someone help me to determine the space complexity? I need briefly to elaborate space complexity analysis!

int fib (int n)

{ if (n == 0 || n == 1)

{ return n; }

else

{

int tmp1 = 0, tmp2 = 1, result;

for (int i=2; i<=n; i++)

{

result = tmp1 + tmp2;

tmp1 = tmp2;

tmp2 = result;

}

return result; }

}

and recusive

int fib (int n)

{ if(n == 0 || n == 1)

return n;

else return

( fib (n-1) + fib (n-2) );

}

Explanation / Answer

int fib (int n)

{ if (n == 0 || n == 1)

{ return n; }

else

{

int tmp1 = 0, tmp2 = 1, result;

for (int i=2; i<=n; i++)

{

result = tmp1 + tmp2;

tmp1 = tmp2;

tmp2 = result;

}

return result; }

}

Space Complexity is :o(1).

Here result = fib[i],tmp2 = fib[i-1],tmp1=fib[i-2].

The two assignments  tmp1 = tmp2; tmp2 = result; are after the sum those values are prepared for next itearation.

and recusive

int fib (int n)

{ if(n == 0 || n == 1)

return n;

else return

( fib (n-1) + fib (n-2) );

}

Space complexity is:o(n).

space complexity of recursive algorithm is proportinal to maximum depth of recursion tree generated. If each function call of recursive algorithm takes O(n) space.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.