Good analysis, Danny. It's mainly due to the linear time required by string-append and maybe string-length. If there had been a constant-time string-cons, we would have had linear time. This can still be done by converting to lists: (define (string->mformat-3 str n filler) (let loop ([l (string->list str)] [len (string-length str)]) (if (>= len n) (list->string l) (loop (cons filler l) (add1 len))))) There is still an overhead though, probably from the conversion from a big list to a big string: trial 10000000 2: cpu time: 348 real time: 347 gc time: 36 3: cpu time: 4957 real time: 4959 gc time: 3740 Actually, version 3 is in fact in O(n log n) because of the add1 (maybe also because of len, depending on how it is treated on the loop call). Version 2 is also probably in O(n log n), but maybe there can be some nice compilation trick to prevent that. Although we are of course bounded by the addressable memory space (but Racket programs are supposed to be independent of that, I think). Laurent <div class="gmail_quote">On Fri, Sep 28, 2012 at 10:38 PM, Danny Yoo <<a href="mailto:dyoo@hashcollision.org" target="_blank">dyoo@hashcollision.org</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">> It is also possible to use build-string, without using explicit recursion: > (define (string->mformat str n filler) > (string-append > (build-string (max 0 (- n (string-length str))) > (lambda (x) filler)) > str)) </div>Hi Laurent, I like this one much more because it won't have the quadratic behavior that the first solution will exhibit on sufficiently large n. It's neat to see how the two compare in terms of time. Here's a small test program: ########################### #lang racket ;; string->mformat-1: string number char -> string (define (string->mformat-1 str n filler) <div class="im"> (if (equal? (string-length str) n) str </div> (string->mformat-1 (string-append (string filler) str) n filler))) ;; string->mformat-2: string number char -> string (define (string->mformat-2 str n filler) <div class="im"> (string-append (build-string (max 0 (- n (string-length str))) (lambda (x) filler)) str)) </div>;; test: number -> void ;; Just show how the two functions compare. (define (test n) (printf "trial ~a\n" n) (displayln "1:") (time (void (string->mformat-1 "foo" n #\0))) (displayln "2:") (time (void (string->mformat-2 "foo" n #\0))) (newline)) (for ([n '(10 100 1000 10000 100000)]) (test n)) ########################### We'll compare the two versions to see how they perform. Here's what I see on my machine: ########################### trial 10 1: cpu time: 0 real time: 0 gc time: 0 2: cpu time: 0 real time: 0 gc time: 0 trial 100 1: cpu time: 0 real time: 0 gc time: 0 2: cpu time: 0 real time: 0 gc time: 0 trial 1000 1: cpu time: 0 real time: 0 gc time: 0 2: cpu time: 0 real time: 0 gc time: 0 trial 10000 1: cpu time: 141 real time: 152 gc time: 78 2: cpu time: 1 real time: 0 gc time: 0 trial 100000 1: cpu time: 20866 real time: 22001 gc time: 8670 2: cpu time: 2 real time: 2 gc time: 0 ########################### We can see that the performance of string->mformat-1 starts to falter as n grows. The string->mformat-2 function is better because it does not repeatedly use string-append on the accumulated result. </blockquote></div>