What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term?
Posted: Wed Jul 13, 2022 7:40 pm
int fibo(int n)
int fibo_terms[100000] //arr to store the fibonacci numbers
fibo_terms[0] = 0
fibo_terms[1] = 1
for i: 2 to n
fibo_terms = fibo_terms + fibo_terms
return fibo_terms[n]
a) O(1)
b) O(n)
c) O(n2)
d) Exponential
int fibo_terms[100000] //arr to store the fibonacci numbers
fibo_terms[0] = 0
fibo_terms[1] = 1
for i: 2 to n
fibo_terms = fibo_terms + fibo_terms
return fibo_terms[n]
a) O(1)
b) O(n)
c) O(n2)
d) Exponential