Time complexity of system.out.println

Question

I've been told different things over my course on algorithms, and was wondering if I could get a definitive answer as to the time complexity of Java's System.out.println() command.

For example, what would the time complexity of the following be, with respect to N?

String stringy = "";
while(stringy.length() < N) {
    System.out.println(stringy);
    stringy += "X";
}

Thanks for helping out the new guy!

Poppycock

You've got yourself an infinite loop if N is greater than 0. So that would be O(Infinity). The function will not complete. – Povertystricken

It's not an infinite loop. – Coracorabel

The time complexity of these operations is O(n^2). The += is O(N) and you do this N times. – Keifer

I'm not begging for rep or anything, but you've selected a crazily incorrect answer. It has two very incorrect assumptions in it, particularly how it addresses the +=. No Idea For Name's answer has good information in it about the actual complexity of System.out.println. – Goral

Answer 1

the Time complexity of this code is O(N*N) because it's a loop of N times that prints. I don't know what have you been told but the time complexity of printing it not worse then O(N) in Java.

in your code you add "X" to each line, and therefor your printing will be:

X
XX
XXX
XXXX
XXXXX
XXXXXX
.
.
.

so it's complexity is calculated as an Arithmetic progression and we get:

(1+N)*N/2=O(N^2)

to read on how the command work you can read here or here:

There is a general notion that SOPs are bad in performance. When we analyze deeply, the sequence of calls are like println -> print -> write() + newLine(). This sequence flow is an implementation of Sun/Oracle JDK. Both write() and newLine() contains a synchronized block. Synchronization has a little overhead, but more than that the cost of adding characters to the buffer and printing is high.

When we run a performance analysis, run multiple number of SOP and record the time, the execution duration increases proportionally. Performance degrades when we print more that 50 characters and print more than 50,000 lines.

It all depends on the scenario we use it. Whatever may be the case, do not use System.out.println for logging to stdout.

Polk

If you admit that the loop runs N times, and that printing is an O(n) operation, how can you say that the entire code is O(n)? – Goral

@Goral you are absolutely correct, and i haven't finished my morning coffee, i'm gonna edit this and add example – Polk

Answer 2

I have run a basic python program to check the time complexity of the print statement in Python for a variable number of characters to be printed. The code goes as -

import time

def current_milli_time():
    return round(time.time() * 1000)

=====================================

startTime1 = current_milli_time()

for i in range(10000):
    print("a", end="")

endTime1 = current_milli_time()

=====================================

startTime2 = current_milli_time()

for i in range(10000):
    print("ab", end="")

endTime2 = current_milli_time()

=====================================

startTime3 = current_milli_time()

for i in range(10000):
    print("abc", end="")

endTime3 = current_milli_time()

=====================================

print("\nTime(ms) for first case: ", endTime1 - startTime1)
print("Time(ms) for second case: ", endTime2 - startTime2)
print("Time(ms) for second case: ", endTime3 - startTime3)

We can see that in the first case we printed only "a", in the second case we printed "ab" and in the third case we printed "abc", the time complexity increased linearly with the number of characters.

Therefore, it can be said that for every language the print statement takes O(lengthOfString) time.

Supply

Answer 3

time complexity tells you how much more work your algorithm has to do per increment of input size, give or take some constant coefficient.

So an upper bound complexity of O(2 N) is equal to complexity O(23587 N) because the actual definition found here

http://en.wikipedia.org/wiki/Big_O_notation

states that the coefficient can be any number no matter how large, as long as it is fixed with regards to the size of the input.

because you are not using 'N' within the loop, you are just adding a char on to a String, the amount of work per iteration is equal to how many iterations you have -> O(N)

if you had "stringy += stringy;" instead it would be O(N^2) because each iteration you are doubling the amount of work you have to do

**NOTE

I am assuming system.out.print is an atomic statement, ie it prints all the characters as a single action.. if it printed each character individually then its O(N^2)....

Pseudonymous

It's O(N^2) even without println, because adding the character to the string is a linear operation as well. IF you added s += s like you suggest, AND println was constant (which it isn't) than the whole code would be O(n lg n). – Goral

Answer 4

The complexity of this code is O(n^2). It iterates the loop N times, and because System.out.println must print each character, which prints from 0 to N characters each iteration, averaging N/2, you drop the constant, N*N = N^2. In the same manner, adding to the string is going to cause the entire string to get copied (Strings are immutable in Java, so any changes mean you have to copy the entire string into a new string). This is another linear operation. So you have n * (n/2 + n/2) is still on a quadratic order - O(n^2).

String stringy = "";
while(stringy.length() < N) { // will iterate N times
    System.out.println(stringy); // has to print N letters
    stringy += "X"; // has to copy N letters into a new string
}

Goral

Answer 5

A great answer can be found here: http://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N

The main idea is that printing a string is actualy copying it to the stdout - and we know that copy of a string is o(n).

The second part says that you can try printing a large number of times: - one character - A very large string And you will see the time difference!! (if printing would be o(1) you wouldn't)

Transpadane

It is always good consider important part of the link in answer. – Chiliad

Answer 6

Time complexity of System.out.println(stringy); command ???

You basically meant the time complexity of the code snippet above.Look , time complexity is not particularly related to one specific code or language it basically means how much time theoretically will be taken by the line of code. This usually depends on two or three things :

• size of the input
• degree of polynomial (in case of solving polynomial equations)

Now in this part of your code :

String stringy = "";
while(stringy.length() < N) {// the loop will execute in order of N times 
    System.out.println(stringy);//println will execute in order of N times too as in printing each character 
    stringy += "X";
}

It will obviously depend on the size of input which is of course the length of the string. First the while loop executes little less than N (because of the condition stringy.length() < N making it <= will make it run through the full length of the string ) which we can say in the order of N and printing the string will be done in the order of N so overall code will have a running time of O(N^2)

Schreib

Because the time required to run println is also linear, you have a linear operation in a linear loop which makes for a quadratic runtime. – Goral