Prove complexity for a generic algorithm

Question

I'm new to theory of complexity and am trying to prove a fact.

So, let's consider an algorithm T that receive at input an integer n.

That algorithm has a time complexity for n = 1 : θ(1) and for n > 1 : 2T(n/2)+θ(n).

I need to prove that algorithm T(n) has complexity θ(n log(n)). I tried to prove that with mathematical induction but nothing seems to work:

n = 1 -> θ(1)

n = 2 -> 2T(2/2)+θ(2) = 2T(1) + θ(2) = 2θ(1)+θ(2).

n = 3 -> 2T(3/2)+θ(3) = ??

It this approach correct? Is there a better way to understand this?

Answer 1

This specific instance can be solved easily by drawing how the recursive T(n) function is calculated. Each call to T(n) has a cost of θ(n) plus two times the cost of half the problem size.

 T(n) = ...

0:                 θ(n)
                  /   \
1:          θ(n/2)     θ(n/2)
            / \           / \
2:     θ(n/4) θ(n/4) θ(n/4) θ(n/4)
        / \       ⋰⋱  ⋰⋱  ⋰⋱
3: θ(n/16) θ(n/16) ⋯ ⋯  ⋯  ⋯  ⋯ ⋯
   ⋰⋱       ⋰⋱
  θ(1) θ(1)  ⋯  ⋯

Each level has two times the number of terms than the previous level. The whole tree is log₂ n levels deep. So what is the sum of all nodes in this tree? We can describe it as the sum

  2⁰·θ(n/2⁰) + 2¹·θ(n/2¹) + 2²·θ(n/2²) + ⋯ + 2^{(log₂ n)}·θ(1)
= 2⁰·θ(n/2⁰) + 2¹·θ(n/2¹) + 2²·θ(n/2²) + ⋯ + n·θ(n/n)
= Σ_{i = 0 ... log2n} 2ⁱ·θ(n/2ⁱ)
= Σ_{i = 0 ... log2n} θ(n)
= log₂(n) · θ(n)
= θ(n · log n)

(Note: this assumes that a·θ(b·n) = θ(a·b·n) is obvious, which I'd technically have to show in a rigorous proof.)

However, such calculations are impractical to do in the general case. Therefore, we would usually apply the Master Theorem which gives us the complexity if the recursive run time of the form T(n)=a·T(n/b) + f(n) matches a specific pattern. Here a=2, b=2, f(n)=θ(n).

With the Master Theorem, the case matches where c = log_ba = 1 and f(n) = θ(n^c · log^k n) with k=0. This tells us that T(n) = θ(n^c · log^k+1 n) = θ(n · log n). So both paths arrive at the same solution, but the Master Theorem is more general, and also simpler because we only have to match the structure of our recursive function for the run time against three known patterns.

Your approach by induction is not satisfactory, because you aren't performing any induction step. Usually, we show that the induction property must hold for n+1 if it holds for n, therefore it is correct if it also holds for any known n (e.g. n=1). This is excessively uncomfortable to do here, so it would be better to prove that a property holds for 2n if it holds for n. I'll leave this as an exercise for the reader ;) but would like to point out that such an induction would technically only prove this for powers of 2 rather than all n, and a further argument would be needed to generalize this.