To find the time complexity of the recurrence relation \( T(n) = T\left(\frac{n}{2}\right) + n \log n \) using the back substitution (or iterative) method, we will unfold the recurrence step by step. Recurrence: \[ T(n) = T\left(\frac{n}{2}\right) + n \log n \] Step 1: First substitution Substitute \( T(n/2) \) from the recurrence into the original equation. \[ T(n) = \left(T\left(\frac{n}{4}\right) + \frac{n}{2} \log \frac{n}{2}\right) + n \log n \] Simplify \( \log \frac{n}{2} = \log n - \log 2 = \log n - 1 \): \[ T(n) = T\left(\frac{n}{4}\right) + \frac{n}{2} (\log n - 1) + n \log n \] \[ T(n) = T\left(\frac{n}{4}\right) + \frac{n}{2} \log n - \frac{n}{2} + n \log n \] \[ T(n) = T\left(\frac{n}{4}\right) + \frac{3n}{2} \log n - \frac{n}{2} \] Step 2: Second substitution Substitute \( T(n/4) \) into the equation. \[ T(n) = \left(T\left(\frac{n}{8}\right) + \frac{n}{4} \log \frac{n}{4}\right) + \frac{3n}{2} \log n - \frac{n}{2} \] Again, simplify \( \log \frac{n}{4} = \log n - 2 \): \[ T(n) = T\left(\frac{n}{8}\right) + \frac{n}{4} (\log n - 2) + \frac{3n}{2} \log n - \frac{n}{2} \] \[ T(n) = T\left(\frac{n}{8}\right) + \frac{n}{4} \log n - \frac{n}{2} + \frac{3n}{2} \log n - \frac{n}{2} \] \[ T(n) = T\left(\frac{n}{8}\right) + \frac{7n}{4} \log n - n \] General Pattern (k-th step) After \( k \) substitutions, the recurrence looks like this: \[ T(n) = T\left(\frac{n}{2^k}\right) + \left(\sum_{i=0}^{k-1} \frac{n}{2^i} \log n\right) - \left(\sum_{i=0}^{k-1} \frac{n}{2^i}\right) \] 1. The first sum: \[ \sum_{i=0}^{k-1} \frac{n}{2^i} \log n = n \log n \sum_{i=0}^{k-1} \frac{1}{2^i} \] This is a geometric series with the sum: \[ \sum_{i=0}^{k-1} \frac{1}{2^i} = 1 - \frac{1}{2^k} \] So, the first sum becomes: \[ n \log n \left(1 - \frac{1}{2^k}\right) \] 2. The second sum: \[ \sum_{i=0}^{k-1} \frac{n}{2^i} = n \left(1 - \frac{1}{2^k}\right) \] So, after \( k \) steps, the recurrence looks like this: \[ T(n) = T\left(\frac{n}{2^k}\right) + n \log n \left(1 - \frac{1}{2^k}\right) - n \left(1 - \frac{1}{2^k}\right) \] Step 3: Stopping condition The recurrence stops when \( \frac{n}{2^k} = 1 \), i.e., \( n = 2^k \), which means \( k = \log_2 n \). At this point, \( T(1) \) is a constant, so: \[ T(n) = T(1) + n \log n \left(1 - \frac{1}{n}\right) - n \left(1 - \frac{1}{n}\right) \] Since \( T(1) \) is a constant and the terms \( \frac{1}{n} \) become negligible as \( n \) grows large, we simplify: \[ T(n) = O(n \log n) \] Conclusion: The time complexity of the recurrence \( T(n) = T(n/2) + n \log n \) is \( O(n \log n) \).
