Which approach of mine for an algorithm upper bound is correct?

Question

Say we have this algorithm in Python.

def secret(S: list):
   n = len(S)
   while n > 0:
      n = n // 2
      for j in range(n):
         if j in S:
            S.append(j)
   return S

I need to find the strictest upper bound (Big-$O$).
I have two approaches to solve this, which give me different solutions and I would appreciate your help deciding which one is correct!

The first approach:

According to the python documentations, the x in s operator is $O(n)$ where $n$ is the length of the list. (Provided here: https://wiki.python.org/moin/TimeComplexity)

So, at the worst case, in each of the for loop, we search the element $|S|$ times. Say that $|S| = N$, then in each iteration the length of $S$ at the worst case gets bigger by $1$ - because it does contain $j$ each time, and it adds this $j$.

The first iteration of the while loop: $\text{range}(N/2)$

$$ N + (N+1) + (N+2) + \dots + N + \frac{N}{2} = \frac{N^2}{2} + 1 + 2 + \dots + \frac{N}{2} = \frac{N^2}{2} + \frac{\frac{N}{2}(\frac{N}{2} + 1)}{2}$$

At the second iteration of the while loop: $\text{range}(N/4)$

$$N + \frac{N}{2} + (N + \frac{N}{2} + 1) + (N + \frac{N}{2} + 2) + \dots + (N + \frac{N}{2} + \frac{N}{4}) = \frac{N^2}{4} + \frac{N^2}{8} + 1 + 2 + 3 + \dots + \frac{N}{4} = \frac{N^2}{4} + \frac{N^2}{8} + \frac{\frac{N}{4}(\frac{N}{4} + 1)}{2}$$

The $k$-th iteration is by:

$$I_k = \frac{N^2}{2^k} + \frac{N}{2^{k-1}} \cdot \frac{N}{2^k} + \sum_{i=1}^{N/2^k} i$$

and over and over... exactly $\lg(N)$ times.

$$ \sum_{k=1}^{\lg(N)} I_k$$

Which is (if I am not wrong here): $$O(N^2 \lg (N))$$

The second approach:

The second approach is like the first, but I noticed that while it's true that the x in S operator is $O(|S|)$, it is not $|S|$ (the current size) in this case specifically, as we insert these numbers if they are already in the array! so each iteration will be at most $O(N)$ and not $O(|S|)$

And so the math gets easier and we do on the first iteration:

$$\overset{N/2 \text{ times}}{N + N + N + \dots + N} = N^2 / 2$$

On the second iteration it would be:

$$\overset{N/4 \text{ times}}{N + N + N + \dots + N} = N^2 / 4$$

and this keeps going of course, $\lg(N)$ times, so we have this sum:

$$ \sum_{k=1}^{\lg(N)} N^2 / 2^k$$

Which at the end goes to be:

$$O(N^2)$$

---

Which one is correct?

When we recognize the 'live' updating size of $N$ (starting at $N$, then $N+1$, then all the way to $N+N/2$, then $N+N/2+1$ all the way to $N+N/2+N/4$, ...)

Or not recognize the live updating size, as the in operator would surely find the number at most $N$ iterations? ($N$ is the starting size of $S$.)

Answer 1

A simple proof of $\Theta(N^2)$ time-complexity

Each iteration of the while loop will cut $n$ in half and, at worst, increases the size of $S$ by $n$. In the $i$-th iteration of the while loop, $n\le\frac{N}{2^i}$.

Hence the line S.append(j) can be executed at most $N/2 + N/4 + N/8+\cdots = N$ times. So, $|S|$ is at most $N + N= 2N$ at any time.

Each appendment takes $O(1)$ time except possibly when the capacity of $S$ is doubled, at which time the appendment takes $O(N)$ time, assuming the usual implementation of Python. So, the total time that is spent on that line is at most $O(N)$.

Now consider the total time spent on if j in S. Each execution will take at most $|S|$ time. So the total time is no more than $$ \frac{N}2 (2N) + \frac{N}{2^2}(2N) + \frac{N}{2^3}(2N) + \cdots = 2N^2$$

Hence, $O(N^2)$ is an upper bound.

---

Consider the first iteration of the while loop, which is basically

      for j in range(N//2):
         if j in S:
           # 

If j is not in $S$, if j in S will take $\Theta(|S|)$ time. In order to execute if j in S faster, we can assume all js are in $S$. Since it takes different number of lookups to find different js, the least total number of lookups needed to execute if j in S for j in range(N//2) is $$1 + 2 + \cdots + (N//2-1)=\Theta(N^2).$$

Hence, $\Omega(N^2)$ is a lower bound.

---

So, the time-complexity is $\Theta(N^2)$.

In particular, the strictest upper bound in big $O$-notation is $O(N^2)$.

"You can improve the bound in your first approach"

Let us do the math more carefully.

The $k$-th iteration is by: $$I_k = \frac{N^2}{2^k} + \frac{N}{2^{k-1}} \cdot \frac{N}{2^k} + \sum_{i=1}^{N/2^k} i$$

So, $$I_k = \frac{N^2}{2^k} + \frac{N^2}{2^{k}}\frac1{2^{k-1}} + \frac N{2^k}(\frac N{2^k}+1)/2= \frac{N^2}{2^k}(1 + \frac1{2^{k-1}}+\frac1{2^k}+\frac1N)\lt\frac{N^2}{2^k}(1+1+1+1)=\frac{4N^2}{2^k}$$

So, $$ \sum_{k=1}^{\lg(N)} I_k\le 4N^2\sum_{k=1}^{\infty}\frac1{2^k}=4N^2.$$