Какова временная сложность следования?

Question

int j = 0;
       for(int i = 0; i < n; ++i) {
           while(j < n && arr[i] < arr[j]) {
               j++;
           }
       }

Кто-нибудь может объяснить его временную сложность более интуитивным способом?

Answer 1

   int j = 0;
   for(int i = 0; i < n; ++i) {
       while(j < n && arr[i] < arr[j]) {
           j++;
       }
   }

В данном коде значение переменной j инициализируется как 0 вне обоих циклов. Внутри l oop значение переменной j всегда увеличивается. Если arr[i] < arr[j], то значение j увеличивается на 1, в противном случае содержимое внутреннего l oop будет выполнено. Обратите внимание, что значение j никогда не может превышать n. Следовательно, сложность данного фрагмента кода всегда O (n) .