Блог

Для чего здесь нужна временная сложность n ? Я чувствую, что внешний цикл-это логн, а внутренний-логн, поскольку они оба имеют x и y увеличиваются в квадрате два с каждым шагом, но возможно ли, чтобы и внешний, и внутренний были sqrt n и были вместе O(n) .

Совершенно ясно, что внешний цикл будет выполняться ровно sqrt(n) раз. Для каждого из внешних циклов существует внутренний цикл, который также выполняется ровно sqrt(n) раз. Таким образом, общее время составляет sqrt(n)*sqrt(n), что, как вы заметили, равно n.