Find the time complexity of the given negative recurrence relation
I don't think your
T can represent a time complexity since many of its values are negative. I assume your question is actually "what is the complexity of
The solution to your recurrence relation, for n>3 is
T(n) = n if
n is odd,
n is even.
The induction is easy: for even
T(n) = T(n-3) + T(n-2) - T(n-1) = n-3 + 4-(n-2) - (n-1) = 4 - n
T(n) = T(n-3) + T(n-2) - T(n-1) = 4-(n-3) + n-2 - (4 - (n-1)) = 4 - n + 3 + n - 2 - 4 + n - 1 = n
And the base case needs checking for
T(4), T(5), T(6), which are
0, 5, -2 respectively.
Thus T(n) = O(n).作者: Paul Hankin 发布者: 15.09.2017 06:36