Find the time complexity of the following program:

var count = 0

var n = 100

for(var i = n; i>0; i/=2){

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

count ++

}

}

Comment your answers. Also try to explain your answer.

Hint: Answer is not O(n^2)

Find the time complexity of the following program:

var count = 0

var n = 100

for(var i = n; i>0; i/=2){

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

count ++

}

}

Comment your answers. Also try to explain your answer.

Hint: Answer is not O(n^2)

4 Likes

The time complexity of the given program is O(n)

The outer loop runs log2(n) times because `i`

is divided by 2 in each iteration until it becomes less than or equal to 0. This results in log2(n) iterations.

The inner loop runs for `n`

times in the first iteration, `n/2`

times in the second iteration, `n/4`

times in the third iteration, and so on. So, the total number of times the inner loop runs is `n + n/2 + n/4 + .. + 1`

, which is equal to `2n`

which is proportional to n.

Therefore the total time complexity of the program is O(log2(n) * 2n) = O(n)`.

Thank you!

3 Likes

The time complexity for this program is O(n).