This proof is for Advance Algorithm.

Please explain and show your work in detail.

Thanks

4. The following recurrence arises in the design of sorting networks. Prove using substitution method that the recurrence is S (n) - O(n log*2 (n)): S(n) - 2 S (n/2) + n log(n), for n > 1, solution to the following