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

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

• You can improve the bound in your first approach. Use the fact that geometric series converge. Apr 6 at 17:52
• @YuvalFilmus But all along the first approach is wrong no? Because it is not correct that in the second iteration overall takes $O(N+1)$ because the number $j$ would be found in $O(N)$ each iteration Apr 6 at 17:55
• And so the second iteration overall and third, they are not going to take $O(N+2)$ and $O(N+2)$ because they would be found beforehand, in the first $N$ elements, so it would be $O(N)$, so which approach is correct? Apr 6 at 17:58
• I didn’t read it deeply enough. Apr 6 at 17:58
• @YuvalFilmus Would appreciate your kind help! :) Apr 6 at 18:00

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

• In the first approach, i took the fact that if we find the number in the list, we add it, and thus if in the first iteration the in operator took $O(N)$ the second one would take $O(N+1)$ and so on.. and the maths get $O(N^2 \lg(N))$. The second approach says this: if we find the number, it is already in the first $N$ elements, and if it is not there, we wont add it and it would take $O(N)$. thus we can say in this situation the in operator takes $O(N)$ (starting value of $|S|$) and not the "updating" size of $S$. So which approach is more correct in your opinion? Apr 7 at 4:50
• @fastttt, please come here for a chat. Apr 7 at 5:07
• Thank you so much! :) Apr 15 at 23:17
• @fastttt You are welcome! Apr 15 at 23:22