使用递归关系的算法时间复杂度

关于使用递归关系分析时间复杂性,我有两个问题。

问题1。使用记忆时,如何形成算法的递归关系?这可能吗?

fib(n)
    if n < 2
        return n
    else
        return fib(n-1)+fib(n-2)

这段代码的递归关系为:

该代码的记忆版本为:

MemFib(n)
    if n < 2
        return n
    else
        if F[n] is undefined
            F[n] = MemFibo(n − 1) + MemFibo(n − 2)
        return F[n]

http://jeffe.cs.illinois.edu/teaching/algorithms/ . 该算法见第5章-动态规划)

现在在我看来,递归关系与第一个例子(T(n-1)+T(n-2)+c)相同,这显然是错误的。你怎么写这个的递归关系?因为我们不总是执行递归调用,所以有可能为此编写一个关系吗?如果这是不可能的,你将如何证明时间复杂度是O(n)形式?

T(n)=a T(不适用)+c T(n/d)+x?

这里x是一个常数。