Действительно ли печать массива O (n) вместо O (1)?

Question

В соответствии с этой проблемой в Cracking The Coding Interview печать массива - это O (N), но я не понимаю, почему это не O (1). У нас есть этот код:

void permutation(String str) {
    permutation(str, "");
}

void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i= 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

И в объяснении говорится:

Executing line 7 takes 0( n) time since each character needs to be printed.

Почему это так? Насколько я знаю, печать всегда O (1). Когда вы печатаете массив, он делает все сразу, если только вы не используете цикл for для печати каждого отдельного символа.

Я что-то упустил?

Answer 1

Нотация Big-O не говорит явно, что она измеряет. Вы можете говорить об алгоритмах, которые занимают O (n) памяти или O (n) системных вызовов. Но объяснение здесь проясняет, что мы говорим O (n) время . Это правильно - O (1) системные вызовы для печати O (n) символов займут O (n) время.