Find the time complexity of the given negative recurrence relation

algorithm time-complexity relation recurrence

65 观看

1回复

4 作者的声誉

what will be the time complexity of recurrence relation
T(n) = T(n-3) + T(n-2) - T(n-1) if n>3 otherwise T(n)=n

作者: Dushyant Arya 的来源 发布者: 2017 年 9 月 15 日

回应 1


1

34356 作者的声誉

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 T".

The solution to your recurrence relation, for n>3 is T(n) = n if n is odd, 4-n if n is even.

The induction is easy: for even n

T(n) = T(n-3) + T(n-2) - T(n-1)
     = n-3 + 4-(n-2) - (n-1)
     = 4 - n

For n odd:

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 发布者: 2017 年 9 月 15 日
32x32