Теорема Ламе. Google it.

Зря минусуете. Не зная о теореме Ламе, трудно найти информацию в интернете об этом. Я например не нашел. Меня тоже этот вопрос заинтересовал, спасибо вышестоящему комментарию за ответ

есть такой вариант док-ва http://pmpu.ru/vf4/numtheory/lame. Хорошего строгого я не встречал, насколько помню. ну и есть логически-интуитивный. при условии, что вы как-то догадались, что числа Фибоначчи — худший случай (опять же логически-интуитивно понятно), то, исходя из их экспоненциального роста, логически-интуитивно понятен логарифм. но, лично я, сам бы не осилил... есть еще забавный математический факт, который тоже нетрудно понять: gcd(fib(i), fib(j)) = fib(gcd(i, j)).

Попробую-ка я кратенько доказать. Пусть a > b. Рассмотрим два шага:

Так как a = kb + a_new,  k ≥ 1,  a_new < b ≤ kb, то и аналогично .

Таким образом после каждых двух шагов наша пара уменьшается не менее чем в 2 раза, а это уже не хуже, чем логарифмическая асимптотика.

Ну и легко показать, что для соседних чисел Фибоначчи F(n) и F(n + 1) количество итераций равно n + 1, что собственно и есть логарифм.

Всем большое спасибо, вы мне очень помогли.

ну а в среднем какая оценка?
для случайных чисел меньших N