Is the time complexity of this algorithm Θ(n)?

Question

I want to find the time complexity of the following algorithm

for i=1 to n do
    j=i
    while j<n do
        j=2*j

I did my calculations and I found that T(n) = log(n^n/n!).

But the correct answer is supposed to be T(n) = Θ(n).

Was I wrong? Or maybe log(n^n/n!) = Θ(n)?

Answer 1

The thing is that your formula is equivalent to theirs. You only need to know some math:

Where first 2 transformations are just basic log properties, and the third is Stirling's approximation.

And clearly everyone knows that n = Θ(n)

Answer 2

Alternative proof could be:

Where

Answer 3

The complexity is Θ(n). The exact runtime is 2n

Check this out:

import math

def get_complexity(n):
    counter = 0

    for i in range(1,n):
        j = i
        while j < n:
            j = 2 * j
            counter += 1

    print('n: %16d\niterations:  %6d\n2n:  %14d \n' % (n, counter, 2*n))


for ten in range(1,5):
    get_complexity(10 ** ten)

output:

n:               10
counter:         16
2n:              20

n:              100
counter:        194
2n:             200

n:             1000
counter:       1990
2n:            2000

n:            10000
counter:      19990
2n:           20000

n:           100000
counter:     199988
2n:          200000