I want to identify the time complexity of the loops below.

Are these the right thoughts about time complexity?

Loop 1

for (auto i = 1; n > 0; n -= i, i  =2) {}

My thoughts: O(n)

Because i has only linear changes and if n --> infinity, then n-i doesn't matter.

Loop 2

for (auto i = 1; n > 0; n -= i, i  = i / 2) {}

My thoughts: O(n)

Because we have a geometric progression of i:

i_n = i_1 *(3/2)^(n - 1)
    

CodePudding user response：

The first is O(√