Reply To: Maths
Recently I came across a very interesting fact about the time complexity of Euclidean algorithm about how the number of steps in the algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.
So if the algorithm took N steps, the smallest number b satisfies
b >= F_(n+1) >= φ^(n-1)
Where F_n in the nth Fibonacci number and φ is the golden ratio. I find it fascinating that the golden ratio somehow shows up here in the worst-case complexity of the algorithm finding the gcd of two numbers.
Does anyone have any good explanations or reading suggestions that explain how and why φ shows up here?