Before revision:  With n denoting the number of tuples in the database, we guarantee  that for every value of k, the k top-ranked answers are returned in \mathcal{O (n polylog n + k  k) time and \mathcal{O n + k) space .
After revision:  With n denoting the number of tuples in the database, we guarantee that for every value of k, the k top-ranked answers are returned in \mathcal{O (n polylog n + k \log k) time and \mathcal{O n + k) space .