6

Assuming that I'm printing a string, as follows:

printf("%s", s);

What can we assume the asymptotic complexity of this function is?

Is it O(n) where n is strlen(s) - it's length? Or is it somehow O(1), constant time. Or something different? I supposed you'd need to know how printf tends to be implemented, however. Any insight is appreciated!

(I should clarify that I'm talking about C rather than C++ but I doubt they're implemented differently)

Edit: added formatting string to printf()

sasha.sochka
  • 14,395
  • 10
  • 44
  • 68
Migwell
  • 18,631
  • 21
  • 91
  • 160
  • 1
    The proper syntax is `printf("%s", stringName);`. – Sukrit Kalra May 29 '13 at 15:09
  • Is there a good reason for that? After all, s is already a string, so why does it need to be formatted by printf? – Migwell May 29 '13 at 15:10
  • 3
    @Miguel yes because it _may_ contain formatting codes itself and that will produce an undefined/unknown/unpredictable/probably_very_bad result. – Adriano Repetti May 29 '13 at 15:13
  • 1
    `s="%d"; printf(s);` will cause boom. Complexity is O(n) obviously – Dmitry Galchinsky May 29 '13 at 15:13
  • Yes. As @DmitryGalchinsky says, the complexity will be O(n), since it would have to print each letter to the screen, for that it would have to go to it's memory location, and hence, it will be O(strlen(s)). – Sukrit Kalra May 29 '13 at 15:15
  • Even if it was implemented like: fwrite(s, 1, strlen(s), stdout)? I thought that was O(1) – Migwell May 29 '13 at 15:17
  • Why? In the count you give `strlen(s)` which itself points out that it is O(strlen(s)). – Sukrit Kalra May 29 '13 at 15:21
  • I just assumed that copying chunks of memory of a known size was faster, like in memcpy(), but as this thread has told me: http://stackoverflow.com/questions/362760/how-do-realloc-and-memcpy-work that is not the case (it is faster, but not in orders of magnitude) – Migwell May 29 '13 at 15:25

1 Answers1

7

It's complexity is O(m + n), where m is the size of the input and n is the size of the output.

If not passing additional parameters like in your case time complexity is O(2*m) = O(m).

But be aware that your code can fail, because s may contain formatting codes itself and that will produce an undefined/unknown/unpredictable/probably_very_bad result as pointed out by Adriano.

sasha.sochka
  • 14,395
  • 10
  • 44
  • 68
  • So you're saying it iterates through each character once when it's formatting, then once when it's outputting? Can't it just memory dump to an output stream, or is that O(m) anyway? – Migwell May 29 '13 at 15:21
  • 1
    I always thought `printf` just output the results as is, when it encountered a `%d` or a `%s`, it would take the appropriate argument and print it out, hence, it's complexity would be linear in it's first argument. – Sukrit Kalra May 29 '13 at 15:28
  • @SukritKalra but printing out a string is not O(1). – effeffe May 29 '13 at 15:35
  • I meant linear in the length of the first argument. So, O(n) – Sukrit Kalra May 29 '13 at 15:36
  • @SukritKalra I'm not sure I'm understanding you: the complexity of the entire function does not only depends on the format string, but also on the length of the other arguments that have to be printed, which is arbitrary and quite independent from the format string; and there could be many arguments. – effeffe May 29 '13 at 16:36
  • @effeffe, you're correct, that's why complexity is O(m+n) when arguments are present. – sasha.sochka May 30 '13 at 12:33