educative.io

Educative

Inner Loop Complexity in Nested For Loop With Index Modification

Section : Common Complexity Scenarios .

How can the complexity of the inner loop be : 2(2n-3) + 2 +c(2n-3) ?

Shouldn’t it be 2(2n-3)+1+log(n-1) + c(2n-3) ?

My explanation :

Initialization of j would occur for log(n-1) times(equal to number of times outer loop will run)
Conditional checking j<i would run for (2n-3) + 1
Increment operator j++ would run for 2n+3 times

Hence, total running time would be 2(2n+3)+1+log(n-1)+c(2n-3).