CODEWITHSUNDEEP
ctimeprintfbig-ocomplexity-theory
LordFenerSSJ
LordFenerSSJ

Reputation: 305

Time Complexity of a printf()?

I'd like to determine time complexity of a printf such as:

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

Or:

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

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

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

void swap(...)

{

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

}

Every 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 function?

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?

Upvotes: 5

Views: 9378

Answers (4)

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40594

Generally, the complexity of printf() is O(N) with N being the number of characters that are output. And this amount is not necessarily a small constant, as in these two calls:

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

The length of myString does not necessarily have an upper bound, so complexity of the first call is O(strlen(myString)), and the second call will output width characters, which can be expected to take O(width) time.

However, in most cases the amount of output written by printf() will be bounded by a small constant: format strings are generally compile time constants and computed field widths as above are rarely used. String arguments are more frequent, but oftentimes allow giving an upper limit as well (like when you output a string from a list of error messages). So, I'd wager that at least 90% of the real world printf() calls are O(1).

Upvotes: 2

Pavel Šimerda
Pavel Šimerda

Reputation: 6163

It is strange to try to evaluate time complexity of printf() as it's a blocking input/output operation that performs some text processing and performs a write operation via a series of write() system calls through an intermediate buffering layer.

The best guess about the text processing part is that the whole input string must be read and all arguments are processed so unless there's some black magic, you can assume O(n) to the number of characters. You're usually not expected to feed the format argument of printf() dynamicaly and therefore the size is known, therefore finite and therefore the complexity is indeed O(1).

On the other hand, the time complexity of a blocking output operation is not bounded. In blocking mode, all write() operations return either with an error or with at least one byte written. Assuming the system is ready to accept new data in a constant time, you're getting O(1) as well.

Any other transformations also occur lineary to the typically constant size of the format or result string, so with a number of assumptions, you can say it's O(1).

Also your code suggests that the output only occurs to actually test the functionality and shouldn't be considered part of the computation at all. The best way is to move the I/O out of the functions you want to consider for the purpose of complexity, e.g. to the main() function to stress that the input and output is there just for testing out the code.

Implementation of the O(1) swap function without I/O:

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

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;
}

Upvotes: 2

Patrick Collins
Patrick Collins

Reputation: 10574

I don't think this is really a sensible question to ask, because printf's behavior is mostly implementation-defined. C doesn't place any restrictions on what the system decides to do once it hits printf. It does have a notion of a stream. Section 7.21 of the C11 standard states that printf acts over a stream.

C lets the implementation do anything that it wants with streams after they're written to (7.21.2.2):

Characters may have to be added, altered, or deleted on input and output to conform to differing conventions for representing text in the host environment. Thus, there need not be a one- to-one correspondence between the characters in a stream and those in the external representation

So your call to printf is allowed to write out 1 TB whenever a char is printed, and 1 byte whenever an int is printed.

The standard doesn't even require that the write happen when printf is actually called (7.21.3.3):

When a stream is unbuffered, characters are intended to appear from the source or at the destination as soon as possible. Otherwise characters may be accumulated and transmitted to or from the host environment as a block. When a stream is fully buffered, characters are intended to be transmitted to or from the host environment as a block when a buffer is filled... Support for these characteristics is implementation-defined.

And the standard doesn't specify whether stdout is buffered or unbuffered. So C allows printf to do pretty much whatever it feels like once you ask it for a write.

Upvotes: 3

Avinash
Avinash

Reputation: 497

The time complexity means not how many time required to run particular program. The time complexity is measured in number of frequencies it requires to run. Now if you are considering the simple printf() statement then obviously time complexity will be O(1).

Refer: Time Complexity For Algorithm

Upvotes: -3

Related Questions