#
#	Number of comparisons for partial match in k-d trees
`expand/C` := proc() C(paramseq) end;

eq1 := (n+1)**2 * C(S,n+1) - n**2 * C(S,n) = 2*n+1 + 2*n*C(NS,n);
eq2 := (n+1) * C(NS,n+1) - n*C(NS,n) = 1 + 2*C(S,n);
patproc := proc(n) option remember; if n<2 then n else Cn fi end;

#	transform to be C(..,n) in terms of C(..,n-1)
eq1 := subs( n=n-1, eq1 );
eq2 := subs( n=n-1, eq2 );
rhs1 := expand( solve( subs( C(S,n)=CSn, eq1), CSn ) );
rhs2 := expand( solve( subs( C(NS,n)=CNSn, eq2 ), CNSn ) );
CS := subs( Cn=rhs1, patproc );

#	Form A matrix
A[1,1] := coeff( subs( C(S,n-1)=x, rhs1 ), x, 1 );
A[1,2] := coeff( subs( C(NS,n-1)=x, rhs1 ), x, 1 );
A[2,1] := coeff( subs( C(S,n-1)=x, rhs2 ), x, 1 );
A[2,2] := coeff( subs( C(NS,n-1)=x, rhs2 ), x, 1 );

#	Form B matrix (A=I+B/n)
B[1,1] := n*(A[1,1]-1);
B[1,2] := n*A[1,2];
B[2,1] := n*A[2,1];
B[2,2] := n*(A[2,2]-1);
detB := (B[1,1]-la)*(B[2,2]-la) - B[1,2]*B[2,1];
solve( expand(detB), la );

findla := proc(p,k)
local it, la;
option remember;
(2+la)**p*(1+la)**(k-p) - 2**k;
it := la - "/diff(",la);
la := evalf((k-p)/k);
to 4 do la := it od;
it
end;
