Time complexity of printf ()?

I would like to define the time complexity of printf, for example:

{
    printf("%d",
           i);
}

      

Or:

{
    printf("%c",
           array[i]);
}

      

Is it correct to assume that printf's time complexity is always O (1) or not?

[EDIT]. Let's take a function that changes two values:

void swap(...)

{

      tmp = x;
      x = y;    
      y = tmp;  

}

      

Each assignment expression costs 1 (in terms of time complexity), so T (n) = 1 + 1 + 1 = 3, which means O (1). But what can I say about this feature?

void swap(...)

{

      tmp = x;
      x = y;    
      y = tmp;  

      printf("Value of x: %d", x);
      printf("Value of y: %d", y);

}

      

Can I say that T (n) is still O (1) in this case?

+3


source to share


4 answers


It is strange to try to estimate the time complexity printf()

, since it is a blocking I / O operation that does some text processing and writes through a series of system calls write()

through an intermediate buffer layer.

The best guess about the text processing part is that the entire input string must be read and all arguments are processed, so unless there is any black magic, you can consider O (n) as the number of characters. Usually you don't need to feed the format argument printf()

dynamicaly and so the size is known, so it is finite and therefore the complexity is really O (1).

On the other hand, the time complexity of the lock release operation is not limited. In blocking mode, all operations write()

return either with an error or with at least one byte. Assuming the system is ready to receive new data in a constant time, you get O (1).

Any other transformations also occur linearly with a typically constant format or output string size, so with a number of assumptions you can say this is O (1).

Also your code assumes that the output only occurs for the actual test of functionality and should not be considered part of the calculation at all. The best way is to move I / O out of the functions you want to consider for complexity purposes, eg. to a function main()

to emphasize that entry and exit are only available for code review.

Implementing O (1) swap function without I / O:



void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

      

An alternative implementation without a temporary variable (just for fun):

void swap(int *a, int *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

      

Implementation of the main function:

int main(int argc, char **argv)
{
    int a = 3, b = 5;

    printf("a = %d; b = %d\n", a, b);
    swap(&a, &b);
    printf("a = %d; b = %d\n", a, b);

    return 0;
}

      

+1


source


I don't think this is really a sensible question, because behavior printf

is mostly implementation-defined. C does not place any restrictions on what the system decides to do when it clicks printf

. It has the concept of flow. Section 7.21 of the C11 standard specifies what printf

operates on a stream.

C lets you do whatever it wants with streams after they are written in (7.21.2.2):

Symbols can be added, changed, or removed on entry and exit to conform to different conventions for representing text in the host environment. Thus, there should be no one-to-one correspondence between characters in the stream and external representations

So your call is printf

allowed to write out 1TB whenever printed char

and 1 byte when printed int

.



The standard does not even require writing to be done when printf

actually called (7.21.3.3):

When a stream is unbuffered, characters should appear from the source or destination as soon as possible. Otherwise, characters can accumulate and are transferred to or from the host environment as a block. When a stream is fully buffered, characters are intended to be sent to or from the host environment as a block when the buffer is full ... Support for these characteristics from implementation.

And the standard does not specify whether it is buffered or not bufferedstdout

. Thus, C allows printf

you to do almost anything you want, as soon as you ask it to be written.

+3


source


Typically, the complexity printf()

is O (N), where N is the number of characters to print. And this sum is not necessarily a small constant, as in these two calls:

printf("%s", myString);
printf("%*d", width, num);

      

The length myString

does not necessarily have an upper bound, so the complexity of the first call is O ( strlen(myString)

), and the second call outputs characters width

that would be expected to take O ( width

).

In most cases, however, the amount of output written printf()

will be limited to a small constant: format strings are usually compile-time constants, and computed field widths as above are rarely used. String arguments are more common, but often allow you to give an upper limit (for example, when you output a string from a list of error messages). So, I would say that at least 90% of real world calls printf()

are O (1).

+2


source


Time complexity does not mean as much time as it takes to run a particular program. Time complexity is measured in the number of frequencies it takes to run. Now, if you are considering a simple printf () statement, then obviously the time complexity will be O (1).

See: Time complexity for an algorithm

-3


source







All Articles