Hot answers tagged

2

I think you already have implemented some sort of adjacency list representation of a directed graph. You can use a topological sorting (https://en.m.wikipedia.org/wiki/Topological_sorting) to order the items.


2

Consider the recurrence $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$ which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $k = 0$ (or $k = n$). We will show this while at the same time showing that $T(n) = \frac{n(n+1)}{2}$. The base case, $n=0$, is ...


Only top voted, non community-wiki answers of a minimum length are eligible