# Tag Info

0

The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary. There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some ...

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 ...

0

This last term n should, more precisely, be n-1, not n. It arises out of the fact that for splitting the array into 2 parts: one part consisting of all elements smaller than pivot and another consisting of all elements greater than or equal to pivot, we have to perform exactly n-1 (comparison) operations.

Top 50 recent answers are included