Matematické Fórum

Ahoj můžete mi prosím pomoct s řešením následujícího příkladu ?
Děkuji.

Jednoduchá implementace Euklidova algoritmu pro výpocet nejvetšího spolec-
ného delitele dvou prirozených císel a, b pocítá výsledek následovne:

Euclid(a, b):
    if b = 0 then
         return a
    else if a > b then
         return Euclid(b, a − b)
    else
         return Euclid(a, b − a)
    end if

Jaká je casová složitost tohoto algoritmu?

Poznámka: Jako velikost vstupu uvažujte celkový pocet bitu císel a, b. Predpokládejte, že
aritmetické operace trvají jednotkový cas.