Search code examples
javatime-complexityprintlnsystem.out

Time complexity of system.out.println

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!

Solution

  • 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.