Does printing a string really take O(n)?

Question

I was doing an example from Cracking the Coding Interview and I read that executing System.out.println(prefix); (where prefix is a String) would take "O(n) time since each character needs to be printed". If a similar print statement was placed inside a O(1) algorithm (e.g. hash table lookup, etc.) would it make the entire algorithm O(n)?

Answer 1

When describing the big-O complexity of an algorithm, it is crucial to define what the variables in the expression represent. There may often be several! For instance, looking up an integer in a binary tree, then printing the string associated with that node might be characterized as O(m + log n), where n is the number of objects in the tree and m is the length of the string.

It is always an error to use a single variable to represent multiple different factors (e.g, both the number of elements in a hash table and their size), and doing so will result in plainly absurd results (e.g, a hash table lookup being O(n)).

Answer 2

I had this exact same question from the same example in Cracking the Coding Interview. The line of code being referred is

void permutation(String str, String prefix) {
  if (str.length() == 0) {
    System.out.println(prefix)
  } else {
    // some for loop recursive code
  }
}

Later in the problem it says "How long does each function call take? Executing line 7 takes O9n) time since each character needs to be printed." Line 7 is in reference to the print statement.

Someone else gave a good explanation from Quora: https://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N

To print anything on the screeen one needs to copy it to the "stdout" file. So when we call System.out.println(), it copies the value of its parameter into the stdout file and we know that copying a string will take O(n) where n is the length of the string.
Try this.

for(int i = 0;i < 100000;++i)  
System.out.println("a");

And after that try this.

for(int i = 0;i < 100000;++i)  
System.out.println("asdhasdyasiluftyiufhiuasydfujshaskljdaklsdhkajsasdjhakjshakjsfgajskgjfgdsajfgasdkjgadviuasgdfmnasdbfjgsdyjakdhggggggggcjhasdfjkgsjkdfgsdfhgdsfdsfgalsdkjfdhkagsdjkasdjd");

If System.out.println()'s time complexity is O(1) both the statements will take nearly same time otherwise you'll see the difference. :)

So a print statement is O(n) if n is the length of the string. But if you have a hash table lookup, big O would be n if n is the length of the string.