Time complexity of C++ cout?

Question

What is the time complexity of making a cout << in C++?

If I have a cout in a loop, for example:

for(int i = 0; i < 1000000 ;i++){
     std::cout << i << endl;
}

Without the std::cout << i << endl; would it be much faster the loop?

you can measure it, it differs from platform to other and hardware to other. that is trivial: any instructions consumes time even at least some nano-seconds — Raindrop7, Oct 17 '16 at 22:00
The C++ standard does not specify the complexity of this overload. Without it the loop will definitely be faster; and the compiler may very well remove the remaining useless hulk altogether. — Sam Varshavchik, Oct 17 '16 at 22:01
impossible to say. what if you're at NASA writing instructions to Cassini? it'll take quite a few hours for the data to get there... — Marc B, Oct 17 '16 at 22:03
Yes, without the entire contents of your loop your loop will go faster. Because it will do nothing. — GManNickG, Oct 17 '16 at 22:10
@MarkB's point is really important here. Even in less extreme cases, the time cost of the IO access will almost certainly dwarf the cost of the formatting. Time complexity is very likely unimportant here, other than the flushes forced by `endl` — user4581301, Oct 17 '16 at 22:49
Regarding time complexities and your other question, see [What are the complexity guarantees of the standard containers?](http://stackoverflow.com/q/181693) on Stack Overflow and [Reversible Container](https://www.sgi.com/tech/stl/ReversibleContainer.html) on SGI. — jww, Oct 20 '16 at 09:15

score 4 · Accepted Answer · edited May 23 '17 at 10:29

Time complexity of C++ cout?

The time complexity of cout is O(1). It can be bound by a constant and its not dependent on the data in your example. For a better estimate, we would need to see what is going on inside the insertion operator. For your example with the integer output, I'm guessing its the classic divide-then-ouput, so its O(1), too. The complexity does not increase as the number i gets larger.

The time complexity of for(int i = 0; i < 1000000 ;i++) is also O(1), but the constant is large at 1000000. The complexity does not grow with different sizes of data.

Combined, 1000000 · O(1) is still O(1).

Usually you don't want such a large constant. However, I have seen some algorithms where a constant of 1000000 was better than exponential growth. For example, I recall seeing an algorithm that ran in O(n³). 1000000 · O(n) is a "better deal" then O(n³) when n ≥ 1000 or so. Also see equation solver.

I hesitate to point you towards What is a plain English explanation of “Big O” notation?, but you may as well have a look. The accepted answer is wrong, and all the upvotes appear to be from folks who don't know the finer points of algorithm analysis. There are better answers in the question.

I think this is what I told in my answer.. "For a better estimate, we would need to see what is going on inside the insertion operator." — Pavan Chandaka, Oct 21 '16 at 21:20
@PavanChandaka In regards to the comment, you did not answer the question, you did not even give instructions on how to find the answer, you merely stated: "we would need to see what is going on inside the insertion operator". Also, usually algorithm complexity does not depend on the input, for example, if an algorithm is O(n), given n=10 or n=10000, then the complexity will keep being O(n). Did you mean to say something else? — Mike Szer, Oct 24 '16 at 05:15
if you are printing something in the insertion (<<) operator overloaded function using binary search or some tree operation, do you think still the algorithmic complexity is O(n) — Pavan Chandaka, Oct 24 '16 at 05:34

score 2 · Answer 2 · answered Oct 17 '16 at 22:14

2

It appears to be a common mistake to use std::endl every time you want a new line. This is not necessarily wrong so much as it defeats the built in buffering in streams because it flushes the stream buffer each time that it is inserted onto the stream.

answered Oct 17 '16 at 22:14

Jon Trauntvein

4,453
6
39
69

score 1 · Answer 3 · answered Oct 17 '16 at 22:57

Time complextiy of Cout<<:

It completely depends on what type you are printing, how you overload your "operator<<", what operations you are doing inside "operator<< overloaded function.

ostream& operator<<(ostream& os, const "yourType"& T)

second question: Yes. Obviously. "Jon Trauntvein" provided good info on it.

Time complexity of C++ cout?

3 Answers3