Please help me with Recurrence

general
, ,
1

I have the following recurrence relation and I have no idea how to find it’s time complexity:-

T(n) = T(n-2) + floor((n-2)/2)

I searched through the internet and I got to know about Master Theorem but then I saw that it doesn’t apply to such relationship. I am a beginner and I just can’t understand how to get the time complexity of this recurrence in Big-O. Please help. What is it’s time complexity?

2

T(n)=T(n-2)+f1
T(n-2)=T(n-4)+f2
T(n-4)=T(n-6)+f3
.
.
T(2)=T(0)+0 //n/2 terms
Add all to get: T(n)=T(0)+floor((n-2)/2)+floor((n-4)/2)+floor((n-6)/2)+…+0
For each n each floor can be calculated in O(1) since there are n/2 terms so complexity will be O(T(0)+n/2) or O(n).

2 Likes
3

Thanks @sabrecpp for your help :smiley: