想請問substitution method的歸納法想法
此題 T(n)=T(3n/4)+T(n/5)+n+1
猜T(n)=O(n)，所以要證T(n)<=cn
解答假設T(m)<=cm,for all m<n
對n做強歸納法證明，應該是n<=m成立（此卻是m<n？），然後用前面證n=m+1
不太理解此的強數歸想法，若此用強數歸不是應該用n<=m成立結果去證n=m+1嗎？
課本證明（手機拍不清用打的）：林立宇演算法講義p13
T(n)=T(3n/4)+T(n/5)+n+1 <= c(3n/4)+c(n/5)+n+1 <=c(3n/4)+c(n/5)+n+n
=(c(19/20)+2)n <= cn 當c>=40,n>=1成立 所以T(n)=O(n)
另外這邊的猜是用O，前面用Θ，是因為substitution只能證一邊所以才寫O？
感謝各位