CODEWITHSUNDEEP
big-o
Travelsbyfire
Travelsbyfire

Reputation: 35

Big(o) notation logn or n?

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

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

    }
}

so I just learned that a logN for loop is one that either divides or multiplies in a statement, which the outerloop is doing. However, because the inner loop is incrementing with addition, and that linear time is a higher complexity than logN, would this for loop be considered O(n)?

Upvotes: 1

Views: 77

Answers (1)

King11
King11

Reputation: 1229

The inner function is O(n) because it runs in linear time, and the outer function is O(log n) because i is multiplied by 2 every iteration. So to answer you question, yes the inner loop would be considered O(n) because j++ runs in linear time. But since O(n) is higher complexity than O(log n), then O(n) takes more precedence and the overall run time will be O(n).

Upvotes: 2

Related Questions