What's the difference between Theta(n) and T(n) when considering time complexity?

Question

The professor was discussing the time complexity of merge sort and he divided the whole process into three steps.

1. check whether the size of array is 1 -> time complexity: theta(1)
2. He described the sorting process -> time complexity: 2T(n/2)
3. Merge the tow sorted sequences -> time complexity: theta(n)

I don't understand step 2, why did he describe it as 2T(n/2) instead of 2Theta(n/2)? What's the difference between theta(n) and T(n)?

Here is the link from Youtube: https://www.youtube.com/watch?v=JPyuH4qXLZ0

And it's between 1:08:45 - 1:10:33

Answer 1

What the professor means by T(n), is the exact complexity, i.e. the number of steps the algorithm needs to complete, which actually may vary depending on the implementation. What's more interesting, is the asymptotic complexity, which is here denoted as Θ(n), and shows how fast T grows along with n.

The first step of the mergesort algorithm is to split the array into halves and sort each half with the same algorithm (which is therefore recursive). That step takes obviously 2T(n/2). Then you merge both halves (hence the name), that takes linear time, Θ(n). From that recursive definition T(n) = 2T(n/2) + Θ(n) he derives that T(n) = Θ(nlogn) which is the complexity class of the mergesort algorithm.