Time complexity system.out.println

Question

I was told different things about the course on algorithms, and I was wondering if I could get a definitive answer about the time complexity of the Java System.out.println () command.

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

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

Thanks for helping the new guy!

Answer 1

The time complexity of this code is O (N * N), because it is an N-time loop that prints. I don’t know what you were told, but the complexity of printing time is no worse than O (N) in Java.

in your code you add “X” to each line, and so your print will be:

 X XX XXX XXXX XXXXX XXXXXX . . . 

therefore, complexity is calculated as an arithmetic progression , and we get:

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

To read how the command works, you can read here or here :

There is a general idea that SOPs do not work well. When we analyze deeply, the sequence of calls is similar to println -> print -> write () + newLine (). This sequence stream is an implementation of the Sun / Oracle JDK. Both write () and newLine () contain a synchronized block. Synchronization has a small overhead, but the cost of adding characters to the buffer and letterpress.

When we run a performance analysis, run several SOPs and record the time, the execution time increases proportionally. Performance degrades when we print more than 50 characters and print more than 50,000 lines.

It all depends on the script that we use. Be that as it may, do not use System.out.println to enter standard output.

Answer 2

time complexity tells you how much more your algorithm needs to complete to increase the input size, give or accept some constant coefficient.

So the top-order complexity of O (2 N) is equal to the complexity of O (23587 N), because the actual definition found here

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

declares that the coefficient can be any number, no matter how large it is, if it is fixed relative to the size of the input.

because you do not use 'N' in the loop, you just add char to the string, the amount of work per iteration is equal to the number of iterations you have → O (N)

if you have "stringy + = stringy;" instead it will be O (N ^ 2), because each iteration doubles the amount of work you have to do

* * NOTE

I assume that system.out.print is an atomic operator, i.e. it prints all characters as one action. If he prints each character separately, then its O (N ^ 2) ....

Answer 3

The time complexity of the System.out.println(stringy);

Basically, you meant the time complexity of the code snippet above. Look, time complexity is not specifically related to one particular code or language, basically it means how much time the code line will theoretically execute. This usually depends on two or three things:

• input size
• polynomial degree (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"; } 

This will obviously depend on the size of the input, which, of course, is the length of the string. First, the while loop executes a little less than N (due to the condition stringy.length() < N , forcing it <= to execute it along the entire length of the string), which we can say in order N, and the line will be printed in order N , so the common code will have an O(N^2) runtime

Answer 4

The complexity of this code is O(n^2) . It iterates the loop N times, and since System.out.println needs to print every character that prints from 0 to N characters in each iteration, averaging N / 2, you discard the constant N * N = N ^ 2. In the same way, adding to a string will cause the entire string to be copied (the strings are immutable in Java, so any changes mean that you need to copy the entire string to a new string). This is another linear operation. So you n * (n/2 + n/2) are still in 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 } 

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-ON

The basic idea is that printing the string actually copies it to stdout - and we know that the copy of the string is o (n).

The second part says that you can try repeatedly printing: - one character - A very large line And you will see the time difference !! (if printing would be o (1), you wouldn’t)