怎么证明上面这段递归式子是O(n)

2012-08-26

如何证明下面这段递归式子是O(n)T（n）T（n/5）+T（7n/10）+cn[解决办法]T(n)Cn(1+9/10+(9/10)^2+.....)O(

如何证明下面这段递归式子是O(n)
T（n）<=T（n/5）+T（7n/10）+cn

[解决办法]
T(n)<=C'n(1+9/10+(9/10)^2+.....)=O(n)