complexity analysis - is my analysis correct?

Question

I just did a complexity analysis, I would love to hear some feedback if my thought process is ok:

I learn phyton by the way

the code:

def f(L):
     n = len(L)
     while n > 0:
         n = n // 2
         for i in range(n):
             if i in L:
                 L.append(i)
     return L

my analysis:

the while loop is an O(log n) complexity ( easy to see, since its n/2 then n/2^-2..... n/2^-n
the inner part is the more complex part for me the loop itself is actually the sum of geometric series, where the first element is n,with q= 1/2, and N = log n $$ S_{n:}=n\cdot \sum _{i=1}^{log:n}\left(\frac{1}{2}\right)^i=\frac{n\left(\left(2^{-1}\right)^{log:n}-1\right)}{\frac{1}{2}-1}=\frac{1}{-\frac{1}{2}}+\frac{n}{\frac{1}{2}}=n $$ image of the equation, since latex seem to do problem

and the append is another function with O(n)

so combining everything it should be O(n^2 log n ) the solution that appear in my book say it should be O(n^2), but there is no further explanation I guess that there is something wrong with my inner loop analysis.

thanks to all

user_1196549 · Answer

In the worst case, i.e. L = [0, 1, ... n-1], every i in L will succeed, causing an append. Hence the total cost of the searches is (for n an exact power of 2)

n + n+1 + n+2 + ... n+n/2-1 +
3n/2 + 3n/2+1 + 3n/2+2 + ... 3n/2+n/4-1 +
7n/4 + 7n/4+1 + 7n/4+2 + ... 7n/4+n/8-1 +
...

As the coefficients of n will never exceed 2, and the number of searches is 2n-1, the total is O(n²).

user_14249087 · Answer

I disagree with @Yves Daoust's analysis of time complexity for the following reasons:

Looking at your code, you define the initial state of n based on len(L). So the Maximum runtime of the while loop is n//2 which implies O(n) complexity.
The run time of the if loop is (n/2) which again implies an O(n) complexity

Therefore the Overall runtime is O(n^2) 'worst-case' which is what the Big O analysis is intended to define.

complexity analysis - is my analysis correct?

2 Answers