How to find next fibonacci number if given a fibonacci number?
for eg if n = 8
it’s answer should be 13.
1 Like
What is the required time complexity?
O(1) Time Complexity.
What is the range of n?
Range of n ?
Btw, did you go through this? Trust me, I didn’t extract it from the deep web, just a simple Google search. 
2 Likes
this is the correct way but i remember it’s not accurate for very large value of n’s
(which is why you asked for the range of n right?)
3 Likes
but it only works for smaller values. maximum upto 50
Who told you that. I think it will work for every value.
go through that page and read the comments.
This is the plot of the absolute errors of the values approximated by the formula for values of X \in [1, 82]. The max value of the range is denoted by
MAX in the Python 3 script. You may play with them to see how the values change.
Here's the code
from math import sqrt
from matplotlib import pyplot as plt
MAX = 82 # limit of X
num = (1 + sqrt(5)) / 2 # multiplying factor
# creating the lists
X = [_ for _ in range(1, MAX + 1)] # index
Fib = [1 for _ in range(1, MAX + 1)] # Actual values
Approx = [1 for _ in range(1, MAX + 1)] # Approx values
Err = [1 for _ in range(1, MAX + 1)] # |Real - Approx|
# fill 'em up
for _ in range(2, MAX):
Fib[_] = Fib[_ - 1] + Fib[_ - 2]
for _ in range(1, MAX):
Approx[_] = int(Fib[_ - 1] * num)
for _ in range(1, MAX):
Err[_] = abs(Fib[_] - Approx[_])
# X vs Error
# values
print("X\tError")
for _ in range(0, MAX):
print("%d\t%d" % (X[_], Err[_]))
# plot
plt.plot(X, Err, color = 'r')
plt.show()
3 Likes