Time-Complexity Verification: Code with two loops with an index halved at each iteration 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 &gt; 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 &quot;in&quot; 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) ) $
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 &gt; 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 &quot;inside-out&quot; approach as I wanted:
The for-loop's complexity is $ \sum_{i=1}^{n_k} \cdot O(n_0) $ ( Complexity of &quot;in&quot; 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.