Кто-то помогает объяснить большую сложность этого кода Java, я так запутался

Question

for(int i = n; i > 0; i--) { 
     for(int j = 1; j < n; j *= 2) { 
     for(int k = 0; k < j; k++) { 
      ... // constant number C of operations 
      } 
     } 
     } 

для этого кода N = 2^m, а правильный ответ - O (N^2). мой профессор сказал, что средняя и внутренняя петли зависят друг от друга, поэтому средняя петля и внутренний петля образуют ряд 2^0 + 2^1 + 2^2 + ... + 2 (log (N)), сумма этого ряда равна 2N. Таким образом, две внутренние петли вместе образуют 2N. 2N * n^2 = O (n^2). Кто-то, пожалуйста, объясните мне эту часть, как мой профессор получил ответ 2N? потому что я думал, что это будет Log N * N для внутренних и средних циклов.

но с моей точки зрения, не я просто беру большой О для каждого цикла, начиная с внешнего, N * log N * n = n^2 * log N. Почему мой путь неправильный? и как узнать, когда плюсом или умножить.

Answer 1

Первый цикл повторяет N раз, второй цикл выполняет итерацию log n раз, так как j удваивает каждый цикл.

Для каждой итерации второго цикла третий цикл повторяет j раз. то сначала он повторяет 1 раз, так как j равен 1, когда j становится 2, он выполняет итерацию 2 раза, когда j становится 4, итерации 4 раза ..... , тогда эти две петли повторяются 1 + 2 + 4 + ... 2^войти п = 2 * N - 1

Тогда время всей программы N * (2 * N - 1) = O (N^2)