再帰ありとなし（for文）でn番目のフィボナッチ数を求めるプログラムをpython3.6で書いています。
プログラムの時間計算量をオーダ記法で書くために、プログラム上で確認する方法を探しています。

現在は目視で
再帰ありだとO（1+1+n-2)=O(n)
再帰なしだとO(1+1+3*n)=O(n)
と計算量を考えています。

しかし、フィボナッチ数列のアルゴリズムと計算量の参考Webページでは、
再帰ありのn番目のフィボナッチ数を求めるプログラムの計算量は
O( ((1 + sqrt(5)) / 2)n-1 )（つまりO(2^n)？）と書かれています。

現在目視で行っている計算量計算のどこが間違っているのか、そしてそれはプログラムで何かを実装することで確認可能なのか教えていただきたいです。

該当のソースコード
再帰あり

def fibrecursive(n):
    if n == 0:
        return 1 #1
    elif n == 1:
        return 1 #1
    else:
        return fibrecursive(n-1) + fibrecursive(n-2)#n-2

if __name__ == '__main__':
    ans = fib(6)
    print(ans)

再帰なし

def fibnormal(n):
    f = 1 #1
    x1 = 1 #1
    for i in range(2, n, 1): #3*n
        x2 = x1
        x1 = f
        f = x1 + x2
    return f

if __name__ == '__main__':
    ans = fib(6)
    print(ans)

試したこと
数学的に考えると
再帰ありのフィボナッチ数列は以下の漸化式になり（cはnに関係ない定数）

T(n) = c (n=0 or 1のとき)

T(n) = T(n-1) + T(n-2) + c (n>=2のとき）

n>=2の時のO(n)を展開すると以下のようになり、再帰ありのフィボナッチ数列の計算量がO(n)なのかO(2^n）なのかもしくは別の記述になるのか更にわからなくなってしまいました。

T(2) = T(2-1) + T(2-2) + c = c + c + c = 3c
T(3) = T(3-1) + T(3-2) + c = T(2) + c + c = 5c
T(4) = T(4-1) + T(4-2) + c = T(3) + T(2) + c = 9c
T(5) = T(4) + T(3) + c = 15c