Practice Problem for DSA Basics

,

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) :slight_smile:

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).