[15] Let be a CNF formula over variables X1,...,Xn, containing n clauses, and with at least k literals in each clause, and with each

[15] Let φ be a CNF formula over variables X1,...,Xn, containing n clauses, and with at least k literals in each clause, and with each variable Xi appearing in at most 2k−d clauses where d is a large enough constant. Then, φ is satisfiable and the exact running time of the above algorithm is at most n log n.

Comments. Hint: truncate each clause in φ to contain exactly k literals.
Since each clause is a disjunction, this does not harm satisfiability. Use the proof of Theorem 6.13.1.