What is a time complexity of the following algorithm in Big Theta Notation?

Question

res = 0
for i in range (1,n):
    j = i
    while j % 2 == 0:
        j = j/2
        res = res + j

I understand that upper bound is O(nlogn), however I'm wondering if it's possible to find a stronger constraint? I'm stuck with the analysis.

Answer 1

Some ideas that may be helpful:

• Could create a function (g(n)) that annotates your function (f(n)) to include how many operations occur when running f(n)

def f(n):
    res = 0
    for i in range (1,n):
        j = i
        while j % 2 == 0:
            j = j/2
            res = res + j
    return res

def g(n):
    comparisons = 0
    operations = 0
    assignments = 0

    assignments += 1
    res = 0

    assignments += 1.     # i = 1
    comparisons += 1.     # i < n
    for i in range (1,n):

        assignments += 1
        j = i

        operations += 1
        comparisons += 1
        while j % 2 == 0:

            operations += 1
            assignments += 1
            j = j/2

            operations += 1
            assignments += 1
            res = res + j

            operations += 1
            comparisons += 1

        operations += 1        # i + 1
        assignments += 1       # assign to i
        comparisons += 1       # i < n ?

    return operations + comparisons + assignments

• For n = 1, the code runs without hitting any loops: assigning the value of res; assigning i as 1; comparing i to n and skipping the loop as a result.
• For n > 1, you get into the for loop, and the for statement is all that is changing the loop varaible, so the complexity of the rest of the code is at least O(n).

Once in the loop:

1. if i is odd, then you only assign j, perform the mod operation and compare to zero. That will be the case for half the values of i, so each run of the loop from 2 to n will (half the time) add a fixed number of a few operations (including the loop operations). So, that's still O(n), just with a larger constant.
2. if i is even, then we divide by 2 until it is odd. This is what we need to work out the impact of.

Based on my counting of the different operations, I get:

• g_initial_setup = 3 (every time)
• g_for_any_i = 6 (half the time, it is just this)
• g_for_even_i = 6 for each time we divide by two (the other half of the time)

For a random even i between 2 and n, half the time we will only need to divide by two once, half the remaining time by two again, half the remaining time by two again, etc. So we have an infinite series as n goes to infinity of sum(1/2^i) for 1 < i < n, and multiply that by the 6 operations done for each halving of j.

I would expect from this:

g(n) = 3 + (n * 6) + (n * 6) * sum( 1 / pow(2,m) for m between 1 and n )

Given that the infinite series 1/2^n = 1, we simplify that to:

g(n) = 3 + 12n as n approaches infinity.

That implies that the algorithm is O(n). Huh. I did not expect that.

Let's try out the function g(n) from above, counting all the operations that are occurring as f(n) is computed.

g(1)        =         3 operations
g(2)        =         9 
g(3)        =        21 
g(4)        =        27 
g(5)        =        45
g(10)       =       123
g(100)      =      1167
g(1000)     =     11943
g(10000)    =    119943
g(100000)   =   1199931
g(1000000)  =  11999919
g(10000000) = 119999907

Okay, unless I've really made a serious error here, it's O(n).