Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Asymptotic complexity of printf

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()

like image 819
Migwell Avatar asked May 29 '13 15:05

Migwell


1 Answers

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.

like image 146
sasha.sochka Avatar answered Sep 23 '22 03:09

sasha.sochka