( We use this algorithm to sort an array A of n elements. We divide A into two subarrays : A1 and A2 having each one n/2 elements, then we divide A1 into A11 and A12 having each one n/2*2 elements .)

1. Give the formula T(n) of a given array of size n by using the running time of its subarrays.

2. If n is an exact power of 2, how many time could we divide the problem in two sub-problems until we reach n problems each one having size 1.

3. Construct a recursion tree for the recurrence T(n) = 2T(n/2)+cn

4. Let T(n)= 2 if n=2

2T(n/2)+n if n= 2k , k>1

Prove by induction that T(n)=nlgn.

*******

We would like to sort 1,000,000 numbers (n =1, 000, 000) on two different machines running different sorting algorithms. To sort n numbers, algorithm A requires operations, while algorithm B requires operations.

Algorithm A will be executed on a slow machine (speed = operations/sec), while algorithm B will be executed on a fast machine (speed = operations/sec). Which one will finish first? Why?