"near linear" is sometimes used to refer to O(n log(n)^O(1)), that is, things that are linear other than a polynomial of log(n). This includes Schönhage–Strasse

"near linear" is sometimes used to refer to O(n log(n)^O(1)), that is, things that are linear other than a polynomial of log(n). This includes Schönhage–Strassen multiplication, with its O(n log(n) log(log(n))) complexity.