(1) string concatenation: step through the list of Char to reach the end, then append the second string; this is linear in the length of "the quick brown fox...".
(2) list concatenation: start with [], append "the quick brown fox...", append "now is the time...". Each concatenation is linear in the number of strings already concatenated, so becomes expensive as more stings are appended.
(3) function composition: (in effect) start with (const ""), compose it with (++ "the quick brown fox...:), compose it with (++ "now is the time..."). Each concatenation is constant time, since it's simply applying (.) to what it has.
I don't understand, since (++) is lazy, the operation itself is very cheap, only traversing the concatenated list need O(n) time complexity, isn't that right?
Yes, but that's precisely what's being avoided. The assumption for ShowS is that you'll have to traverse it anyway to output it; ShowS avoids doing so multiple times.
Now, as to how useful it is... you'll note there isn't actually a lot of code out there that uses ShowS (or functional concatenation in general). The simplistic show/read system uses it, but most other parsers and string generators use other mechanisms instead: Monad, Applicative, occasionally Arrow. (ShowS/ReadS predates all three, I believe. There may have also been additional advantages with pre-monadic/Gofer-style I/O.)
There are also questions of stack/heap complexity; while it may save some time to build up a large output string this way, it also builds up quite a few thunks, whereas (especially with fusion) a more direct concatenation system may have linear heap complexity and constant stack complexity.
(Also, coming at it from a systems perspective, I can't help but think that I/O time dominates concatenation time in the vast majority of cases.)