Final answer:
The tightest complexity of the algorithm represented by the recurrence relation T(n) = 2 · T(n/2) + n is O(n log n), determined by applying the Master Theorem.
Step-by-step explanation:
The given recurrence relation T(n) = 2 · T(n/2) + n represents the time complexity of an algorithm where the problem of size n is divided into two subproblems of size n/2, and the division step has a linear complexity represented by + n. To find the tightest complexity class for this recurrence, we can apply the Master Theorem, which provides a shortcut to solve recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1.
In this case, a = 2, b = 2, and f(n) = n. According to the Master Theorem, we compare f(n) with nlogba, which is nlog22 = n. The function f(n) matches this exactly, meaning we fall into case 2 of the theorem, and the resulting complexity is O(n log n).
Therefore, the tightest complexity of the algorithm is O(n log n), making option (d) the correct answer.