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) = Θ(nlogba logk+1n) when nlogba = 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 logba = n log21 = 1 --> f(n) = Θ(nlogba log1 n)
So the span ends up being: Θ(log2 n).
What I'm wondering is why is k = 1 in this example?
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
.