Short Problem Definition:
You are given an integer, N. Write a program to determine if N is an element of the Fibonacci sequence.
time complexity is O(15√(ϕn−(−ϕ)−n))
space complexity is O(15√(ϕn−(−ϕ)−n))
There are two methods:
A) generate all fibonacci numbers up to N and check if the candidates are in this set.
B) There is a mathematical function that can prove whether a number is in the Fibonacci sequence in sqrt(N) time. I am not going to explain this here. Read the discussion on SO if you are interested.