Compute the complexity of the following Algorithm?

This question already has an answer here:

Big O, how do you calculate/approximate it? 22 answers

---

i = 1;
while(i < n + 1){
    j = 1;
    While(j < n + 1){
        j = j * 2:
    }

    i = i + 1;
} 

outer loop takes O(n) since it increments by constant.

i = 1;
while(i < n + 1){

    i = i + 1;
} 

inner loop : j = 1, 2, 4, 8, 16, ...., 2^k
j = 2^k (k >= 0) when will j stops ?
when j == n,
log(2^k) = log(n)
=> k * lg(2) = lg(n) ..... so k = lg(n).

While(j < n + 1){

        j = j * 2;
}

so total O(n * lg(n))

---

Since j grows exponentially, the inner loop takes O(log(n)) .

Since i grows linearly, the outer loop takes O(n) .

Hence the overall complexity is O(n*log(n)) .

---

This one is similar to the following code :

for( int i = 1;i < n+1 ; i++){ // this loop runs n times
    for(int j = 1 ; j<n+1 ; j=j*2){// this loop runs log_2(n)(log base 2 because it grows exponentially with 2)
      //body
    }
} 

Hence in Big-Oh notation it is O(n)*O(logn) ; ie, O(n*logn)

链接地址: http://www.djcxy.com/p/39346.html

上一篇: 算法

下一篇: 计算以下算法的复杂度？