I am having problem with solving the following recurrence relation. $A$ is a set, there are at most $k+1$ of this set and $|A|$ is at most $n/2$.

$T(n) = O(n log k) + \sum_A T(|A|)$

I guess it can't be solved by the techniques presented in CLRS book (like master theorem), I also tried to solve it using induction on $n$ (I mean the Computational geometry approach) but I failed.


  • $\begingroup$ What is the computational geometry approach? $\endgroup$ – Yuval Filmus Oct 17 '15 at 13:34
  • $\begingroup$ From what I know (and studied in computational geometry), we can solve these problems by induction on their variables. $\endgroup$ – M a m a D Oct 17 '15 at 14:29
  • 2
    $\begingroup$ I don't understand your equation. What do you mean by sum over $A$? Which sets are you summing over? Can't we just assume the worst case, in which we get $T(n) = O(n\log k) + kT(n/2)$? For each fixed $k$, you can solve this using the master theorem. Even for arbitrary $k$ you can solve $T(n) = O(n) + kT(n/2)$ and then multiply the result by $\log k$. $\endgroup$ – Yuval Filmus Oct 17 '15 at 19:10
  • $\begingroup$ @YuvalFilmus thanks for your reply. It is the Lemma 4.4.2 in page 75 of the book Geometric Spanner Networks by michiel smid and Giri Narasimhan. $A$ denotes a few sets and each set contains a few points. When I sum over the $A$ I mean number of $A$s which is $A_1 A_2 ... A_{k+1}$ and $A_i$ contains at most $n/2$ points. The $k$ is not a fixed number, it is a variable.The solution contains $n$ and $k$ variables which is most likely $O(n \log n \log k)$ (even though I couldn't prove it yet), but $k$ is not fixed. $\endgroup$ – M a m a D Oct 17 '15 at 19:48
  • $\begingroup$ Even for fixed $k$, the solution is $O_k(n^{\log_2 (k+1)})$ [correcting $k$ to $k+1$ in my formulation], which is not quite what you wrote. Perhaps there are more constraints on the sizes of the sets. $\endgroup$ – Yuval Filmus Oct 17 '15 at 21:27