数学归纳法证明时间复杂度

1. T(n)=1+∑j=0n−1T(j)

欲证明 T(n)=2n （为了简化问题的方便，这里忽略了问题的背景信息，边界条件： T(0)=1 ）。

已知边界条件： T(0)=20=1 ，由数学归纳法，化结论为条件，则有：

T(n)====1+∑j=0n−1T(j)1+∑j=0n−12j1+20+21+…+2n−11+20(1−2n)1−2=2n