1
$\begingroup$

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.

thanks.

$\endgroup$

closed as unclear what you're asking by D.W. Oct 18 '15 at 0:22

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – No one 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$ – No one 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