Большой О. не уверен, как на него влияет обновление цикла for

Question

Я немного озадачен тем, как обновление цикла for влияет на BIG O

на коде, подобном этому:

  public static void bigO(int n){
    for(int i=n; i>1; i=i/2){
      for (int j=n; j>1; j=j/2){
        sum++;
      }
    }
  }

Я не уверен, как обновление (j=j/2) повлияет на него.

Answer 1

Два цикла for не зависят друг от друга, поэтому общая сложность должна быть примерно равна сложности двух циклов. Каждый цикл равен O(lgN), где lg означает «логарифмическая база 2». Таким образом, умножение этого вместе дает O(lgN*lgN) для общей сложности.

Чтобы лучше понять, откуда O(lgN), рассмотрим входное значение n=16. Внешний цикл for в i будет иметь следующие итерации:

i  | iteration #
16 | 1
8  | 2
4  | 3
2  | 4

lg(16) на самом деле равно 4, потому что 2^4 = 16, так что это подтверждает сложность, которую мы ожидаем. Вы также можете проверить другие значения n, чтобы убедиться в этом. Внутренний цикл в j ведет себя таким же образом и не зависит от внешнего цикла в i.