Как найти временную сложность вложенных для циклов, которая включает логарифмы и правила суммирования?

Question

Итак, я пытался найти временную сложность кода, показанного ниже.Я знаю, что первый цикл for повторяется n раз и должен быть умножен на повторения второго цикла for, чтобы найти сложность с большим временем.Однако условия внутри второго цикла for сбивают меня с толку.

public static void main(String[] args) {
    int x = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j = j * 2) {
            x = x + 1;
        }
    }
}

, если j умножать в 2 раза за каждую итерацию, то временная сложность обоих циклов будет O(nlog(n)).Но так как j останавливается на основании значения i, я предполагаю, что правило суммирования должно быть задействовано.Мое лучшее предположение к общей сложности времени будет O(nlog^2(n)?Прав ли я или нет, и почему?

Answer 1

O (log n ) - это стоимость последнего (худшего) цикла по j, поэтому O ( n log n ) имеет верхний предел .Вопрос в том, меньше ли это, потому что средняя стоимость ниже .Но это не так: это происходит только для сильно выпуклых функций (рассмотрим простой внутренний цикл с i итерациями, где среднее значение является просто постоянным множителем, умноженным на n )и журнал вогнутый.Так что это всего лишь O ( n log n ) в конце концов.