Здравствуйте, infused, Вы писали:

I> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

I>Предпологаю что это порядка log2(max(m,n))... ???
I>Зараннее спасибо.

Кол-во операций = кол-во итераций * кол-во операций в ходе итерации

Кол-во операций в ходе итерации — известно и постоянно => остаётся найти кол-во итераций.
Вэтом нам поможет лемма Ламе, которая гласит, что:

Число итераций, необходимых для вычисления НОД двух натуральных чисел A и B (A>B>0),
мажорируется 5-кратным числом десятичных знаков наименьшего из 2-х чисел.
Т.е. если n-число необходимых итераций, то
n <= 5*(floor(log10(B)) + 1)