# 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 > 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) )$$

• Both approaches are correct, but the second one is not tight enough (because the total complexity of the for-loop is not always $\Theta(n^2)$). – Nathaniel Apr 11 at 21:16
• I find the second approach easier because I worked "inside out", do you any idea of how such an approach might work here in order to give the correct tight bound? – hazelnut_116 Apr 11 at 21:34

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.