Master Theorem case 2 - Constant k

Question

I'm studying for a midterm on Master Theorem and I came across an example for case 2 where k > 0. I understand everything about the theorem except for the constant and how it increments or is calculated.

Case 2 states: T(n) = Θ(n^log_ba log^k+1n) when n^log_ba = f(n) but where does the k come from?

The example in question:

Matrix Multiplication

cilk void Mult(*C, *A, *B, n) {
    float *T = Cilk_alloca(n*n*sizeof(float));
    spawn Mult(C11,A11,B11,n/2);
    spawn Mult(C12,A11,B12,n/2);
    spawn Mult(C22,A21,B12,n/2);
    spawn Mult(C21,A21,B11,n/2);
    spawn Mult(T11,A12,B21,n/2);
    spawn Mult(T12,A12,B22,n/2);
    spawn Mult(T22,A22,B22,n/2);
    spawn Mult(T21,A22,B21,n/2);
    sync;
    spawn Add(C,T,n);
    sync; 
    return;
}

cilk void Add(*C, *T, n) {
  h base case & partition matrices i
  spawn Add(C11,T11,n/2);
  spawn Add(C12,T12,n/2);
  spawn Add(C21,T21,n/2);
  spawn Add(C22,T22,n/2);
  sync;
  return;
}

The span of the addition has been found to be: Θ(log n)

When calculating the span of the multiplication the example states:

M1(n) = M1(n/2) + A1(n) + Θ(1)

A1(n) being Θ(log n) so really: M1(n) = M1(n/2) + Θ(log n)

n log_ba = n log₂1 = 1 --> f(n) = Θ(n^log_ba log¹ n)

So the span ends up being: Θ(log² n).

What I'm wondering is why is k = 1 in this example?

Answer 1

You need to find such parameter k so that the expression Θ(nlogbalogkn) will be Θ(log n). In this case k=1 will satisfy the requirement. It's a matching you need to do in order to get the required form of the expression. More specifically, it's similar to solving an equation logkn = log n for k.