再帰での時間計算量（Python）

Question

実現したいこと

以下のソースコードのオーダー記法での時間計算量が分からず、困っています。
いまいち再帰を用いているソースコードでは求め方が分かりません。
どなたか教えていただけないでしょうか？

def gcd(a, b):
    while a != b:
        if a > b:
            return gcd(a-b, b)
        else:
            return gcd(a, b-a)
    return a

Answer 1

c = 0
#teratail_263673
tt=[]

def gcd(a, b):
    global c
    c+=1
    while a != b:
        if a > b:
            return gcd(a-b, b)
        else:
            return gcd(a, b-a)
    return a

tt[0]=0
for k  in range(1,200):
    for i in range(1,k):
        for j in range(1,k):
            gcd(i,j)
            tt.append(c)
            c=0
    print("{} 範囲での最大呼び出し回数 ={}".format(k,max(tt)))

これを実行した結果、範囲に対して線形にgcd関数の最大呼び出し回数が増えていることから、
計算量がO(n)であることが推定されます。