What is the time complexity of given recurrence relation

Question

1. T(n) = T(n-a) + T(a) + cn

2. T(n) = T(αn) + T( (1-α)n ) + cn

where α, a and c are constant.

Answer 1

1. T(n) = T(n-a) + T(a) + cn

          = T(n-2a) + T(a) + c(n-a) + T(a) +  cn

          = T(n-3a) +T(a) + c(n-2a)+ T(a) + c(n-a) + T(n) +  cn

                 -

                 -

                 -

Terminating condition, n-ka = 0

                        =>         k = n/a.

          = (n/a)T(a) + (c/a)n² - a ( 1 + 2 + 3 + ............. (n/a)th term )

          =  (n/a)T(a) + (c/a)n² - a * (n/a)* (n+a)/2a

          = O(n) + O(n²) - O(n²)

          = O(n²)

2. T(n) =  T(αn) + T( (1-α)n ) + cn    // assuming 0< $a$ < 1.

          = O(nlog n)   // Quick sort algorithm.

Comments

@Vijay. If 'alpha' is 1/2 only then its n.logn   .But value of 'alpha'  can be anything. So, its again O(n^2)

---

assuming 0< a < 1.

I have already mentioned this. 

And yes, If alpha a < = 0 or a > = 1, then it is going to run for an infinite time until stack memory is full because there is no termination point.

The question is not complete. Fast of all it should mention about the range of value of constants and termination point as well. Like T(1) or T(0)= any constant. 

---

Thanks Vijay