Is this a fast implementation of reversing a string? I thought of this algorithm today. It seems fast, but how can I know?

#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include &lt;assert.h&gt;

/*
 * Reverse a string
 * the caller has to free dynamic memory allocated
 */
char *mon_string_rev(char *string)
{
    char *out = malloc ( strlen(string) + 1 );

    assert(out);

    int len = strlen(string);

    int i;

    int counter = 0;

    int iterations = 0;

    while(1) {
        if(len &lt; 0) break;
        // important to only start counting after 
        // determing that the loop will continue
        ++iterations;
        for(i = 0; i &lt; len; i++) {
            // if this is the last character
            // push it onto the output string
            if(i == (len - 1)) {
                out[counter] = string[i];
                counter++;
            }
        }
        len--;
    }
    out[counter] = '\0';

    printf("Total iterations: %d\n", iterations);

    return out;

}

int main(int argc, char **argv)
{

    if(argc &lt; 2) {
        fprintf(stderr, "Usage: %s &lt;string&gt;", argv[0]);
        exit(1);
    }

    char *str = mon_string_rev(argv[1]);

    printf("%s\n", str);

    free(str);

    return !1;

}
Over all, this is good, but there's unfortunately some very major performance problems, and I have a few minor design suggestions.



A string can be reversed quite trivially in linear time. Your algorithm is quadratic.

You can just do a single backwards loop over the input string instead of this convoluted nested loop.



Since mon_string_rev doesn't alter string it should be a pointer to constant character.



Instead of asserting that out isn't null, it might be better to simply return null instead. That allows the caller to handle the error instead of program termination (and when assertions are disabled, it avoids a rather nasty segfault...).



If you're using C99 or newer (and you should be), then declare variables in the tightest scope possible (i.e. declare i in the for loop).



return !1;... what? Just return 0, or, better yet, return EXIT_SUCCESS.



Any time you have an infinite loop terminated by a simple condition, just rewrite it to directly use that simple condition. Terminating 'infinite' loops are very hard to understand when you weren't the person who wrote them, so any time they can be avoided they should be.

Just to illustrate, your loop could instead be: for (; len &gt;= 0; --len) { ... }.



It doesn't really apply here since instrumentation was clearly the main purpose, but in general it's a bad idea to have functions output anything unless their sole purpose is output. (Sorry if you already know this :).)



When it doesn't meaningful affect performance or usability, I like to have the caller manage memory. It's more flexible, and it's more explicit (no question of "wait... do I release this???").