C Sorting The processing time of a sorting algorithm is des

C++ , Sorting

The processing time of a sorting algorithm is described by the following recurrence equation (c is a positive constant): T(n) = 3T(n/3) + 2cn; T(1) = 0 Solve this equation to derive an explicit formula for T(n) assuming n = 3^m and specify the Big-O complexity of the algorithm. Find out whether the above algorithm is faster or slower than usual Mergesort that splits recursively an array into only two sub-arrays and then merges the sorted sub-arrays in linear time cn.

Solution

I am not sure why C++ was mentioned, as it doesn\'t seem to be programming problem

a)

T(n) = 3T(n/3) + 2cn,               and     T(1) = 0.       Assuming n = 3^m

T(3^m) = 3T(3^m-1) + 2(3^m)c

T(3^m-1) = 3T(3^m-2) + 2(3^m-1)c,          giving T(3^m) = 3²T(3^m-2) + 3(2)c(3^m)

T(3^m-2) = 3T(3^m-3) + 2(3^m-2)c,          giving T(3^m) = 3³T(3^m-3) + 2(3)c(3^m)

so we get finally,

T(n) = 3^mT(1) + 2(mc)(3^m) = O(m3^m) = O(nlog₃n)

b)

T(n) for merge sort is :=      O(nlog₂n)

Clearly taking value with log₂ would be bigger than log₃   i.e. Merge sort is slower than given algorithm.

But the trick here is only for large values of n.