I have heard that the worst case for the euclidian algorithm is in the case of Fibonacci numbers. Can this be proven, and can it be proven only n-2 divisions are required (where euclidian algorithm is performed on naturals a, b <= fib(n))?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.