Time-Complexity Verification: Code with two loops with an index halved at each iteration

Question

I have the following code in python and was asked to find the tightest upper-bound in terms of Big-O , I've done two attempts below and I don't know which one is right, can you help me verify as to which one is the right answer/approach?

def f1(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 attempts:
Approach 1:
While loop runs $ log(n) $ times. And at the $ith$ iteration the for-loop runs $ \frac{n}{2^i} $ times; inside the for-loop the conditional runs at most $ O(n) $ times ( because "in" has complexity of $ O(n) $ according to https://wiki.python.org/moin/TimeComplexity ). Thus, the time-complexity of the for-loop is $O(n^2) $. So the time-complexity of total code is: $ \sum_{i=1}^{log(n)} O(\frac{n^2}{2^i}) = O(\sum_{i=1}^{log(n)} \frac{n^2}{2^i} ) = O( n^2 \cdot \frac{1-(1/2)^{1+log(n)}}{ 1-(1/2)^{log(n)} } ) = O(n^2) $

Approach 2:
In the for-loop we have the conditional “if i in L” , the “in” costs $ O(n) $, thus time-complexity of for-loop is $ \sum_{i=1}^{n} O(n) = O( \sum_{i=1}^{n} n ) = O(n^2). $ Looking at the while loop we see that “n” is halved at each iteration because of the statement “n=n//2” . Denote $ n_k = \lfloor \frac{n}{2^k} \rfloor $ as the value of $n$ at the k-th iteration; Disregarding the floor function ( we won't care about $ \pm 1 $ for the value of $ n_k $ since we care about time-complexity ), we'll seek the smallest $ k $ ( we denote $ k $ as the iteration of the while loop ) where $ n_k = 1 \leq \frac{n}{2^k} \iff k \leq log(n) $. Hence the total time complexity of code is $ \sum_{i=1}^{log(n)} O(n^2) = O(log(n)) \cdot O(n^2) = O(n^2 \cdot log(n) ) $

Answer 1

As said above, both approaches are correct but in approach #2 I don't get a tight-bound. Since I want a tight-bound using the second approach I failed to notice what $ n $ actually is once inside the while loop. Let's look at the code above but formatted a bit in the following manner:

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

Analysing the time-complexity of code using "inside-out" approach as I wanted:
The for-loop's complexity is $ \sum_{i=1}^{n_k} \cdot O(n_0) $ ( Complexity of "in" is $ O(n_0) $ ), i.e. $ O( n_k \cdot n_0 ) $. Thus since the while-loop runs $ log(n_0) $ times by my analysis, the total time-complexity of code is $ \sum_{k=1}^{log(n_0)}O(n_k \cdot n_0 ) $ , notice that $ n_k = \frac{n_0}{2^k} $ ( $ k $ is the k-th iteration of while loop ) hence $ \sum_{k=1}^{log(n_0)}O(n_k \cdot n_0 ) = O(\sum_{k=1}^{log(n_0)}n_k \cdot n_0 ) = O(\sum_{k=1}^{log(n_0)} \frac{n_0}{2^k} \cdot n_0 ) = O(n_0^2) $. Denote $ n_0 $ as $ n $ and we have $ O(n^2) $ and we're finished.