Is T(n) >= T(n-1) always true?
I saw a proof for finding complexity of a sorting algorithm which says
something like this :
Total time complexity for the algorithm = T(n-1) + T(n-2)
Thus, Total time complexity for the algorithm <= 2 * T( n-2 )
and further went on to prove some relation.
Ques: Can I always safely assume that T(n) >= T(n-1) ? When I am already
trying to prove the complexity of some algorithm, how can I make this
claim before hand ?
No comments:
Post a Comment