def f():

ans = 0

for (i = n; i >= 1; i /= 2):

for j = m to i:

ans += (i * j)

print(ans)

what is the time complexity of this program ? please help

def f():

ans = 0

for (i = n; i >= 1; i /= 2):

for j = m to i:

ans += (i * j)

print(ans)

what is the time complexity of this program ? please help

It will be in order of O(n)

i think the outer loop would run log n (base 2) times and the inner loop is of O(n)

so it is o(nlogn)

2 Likes