Большая (o) запись в logn или n?

Question

for(int i = 1; i < N; i = 2*i){

    for(j=0; j<i; j++){

    }
}

, поэтому я только что узнал, что logN for loop - это тот, который либо делит, либо умножается в операторе, что делает externalloop. Однако, поскольку внутренний цикл увеличивается с добавлением, а это линейное время сложнее, чем logN, будет ли это для цикла рассматриваться как O (n)?

Answer 1

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