如何化简时间复杂度方程得到T(n) = 3/2 * T(n-1) + 1

原始的第一个等式拆分后包含三部分：

• 固定执行一次的T(n-1)开销
• 50%概率需要额外再执行一次的T(n-1)期望开销，计算为1/2 * T(n-1)
• 固定的常数级操作开销，计为1

把上述三项合并即可得到初始合并式：

T(n) = T(n-1) + (1/2) * T(n-1) + 1

对T(n-1)的同类项做合并，1倍加1/2倍就是3/2倍，最终化简得到目标式：

T(n) = 3/2 * T(n-1) + 1

内容的提问来源于stack exchange，提问作者ml2017