Time-Complexity Verification: Code with two loops with an index halved at each iteration
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.