ѕриступимо тепер до виконанн¤ другоњ частини назви цього пункту - анал≥зу алгоритму ≈вкл≥да. Ќас буде ц≥кавити найг≥рший випадок - коли алгоритм працюЇ особливо довго? як≥ два найменших числа треба дати алгоритму ≈вкл≥да, щоб в≥н працював задане число крок≥в? ¬≥дпов≥дь на це питанн¤ даЇ
“еорема (Ћаме, 1845 р.). Ќехай n Î N , ≥ нехай a>b>0 так≥, що алгоритму ≈вкл≥да дл¤ обробки а ≥ b необх≥дно виконати точно n крок≥в (розпод≥л≥в ≥з залишком), причому а - найменше з такою властив≥стю. “од≥ а=Fn +2 , b =Fn +1 , де Fk - k- те число ‘≥боначч≥.
ƒоказ. –озкладемо a / b у
ланцюговий др≥б: 
,
де q 1 , q 2 ,..., q n - неповн≥ частки з алгоритму ≈вкл≥да; за умовою теореми, њх точно n штук. ¬≥дпов≥дно до властивост≥ 3 пункту 9, континуанти ( q1 q2 ... qn ) ≥ ( q2 q3 ... qn ) взаЇмно прост≥, виходить, ¤кщо (a,b) = d - найб≥льший сп≥льний д≥льник, то
††† ( ª )
ѕом≥тимо, що за смислом к≥нцевого ланцюгового дробу, qn ³ 2, a q1 , q2 ,..., qn -1 , d ³ 1.
ќск≥льки континуанта Ї багаточленом з нев≥дТЇмними коеф≥ц≥Їнтами в≥д ус≥х цих зм≥нних, м≥н≥мальне значенн¤ дос¤гаЇтьс¤ при q1 = q2 =...= qn -1 = d = 1, qn = 2. ѕ≥дставл¤ючи ц≥ значенн¤ в ( ª ), одержимо: а = Fn +2 , b = Fn +1 .
Ќасл≥док. якщо натуральн≥ числа a ≥ b не перевищують N Î N , то число крок≥в (операц≥й д≥ленн¤ з залишком), необх≥дних алгоритму ≈вкл≥да дл¤ обробки a ≥ b не перевищуЇ é log‘( Ö 5 N ) ù - 2, де é a ù - верхнЇ ц≥ле a , F = (1 + Ö 5)/2 - б≥льший кор≥нь характеристичного р≥вн¤нн¤ посл≥довност≥ ‘≥боначч≥.
ƒоказ. ћаксимальне число крок≥в n дос¤гаЇтьс¤ при а = Fn +2 , b = Fn +1 , де n - найб≥льший номер такий, що Fn +2 < N . –озгл¤даючи формулу дл¤ n -ого члена посл≥довност≥ ‘≥боначч≥ (дивитис¤, наприклад, доказ властивост≥ 4 у пункт≥ 9), легко зрозум≥ти, що Fn +2 - найближче ц≥ле до (1/ Ö 5) Fn +2 . «начить (1/ Ö 5) Fn +2 < N , отже, n +2 < log ‘ ( Ö 5 N ), зв≥дки моментально нав≥ть n < é log ‘ ( Ö 5 N ) ù - 3 (саме "м≥нус три", адже розгл¤даЇтьс¤ верхнЇ ц≥ле, тобто, здаЇтьс¤, твердженн¤ насл≥дку можна п≥дсилити).
log ‘ ( Ö 5 N ) ї 4,785 Ј lg N + 1,672, тому, наприклад, з будь-¤кою парою чисел, менших м≥льйона, алгоритм ≈вкл≥да розбираЇтьс¤ не б≥льш, н≥ж за é 4,785 Ј 6 + 1,672 ù - 3 = 31 - 3 = 28 крок≥в.
Ќу от, використовуючи теорему Ћаме, ми провели де¤кий анал≥з швидкод≥њ алгоритму ≈вкл≥да ≥ дов≥далис¤ найг≥рший випадок дл¤ нього - два посл≥довних числа ‘≥боначч≥.
