2
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ You can improve the bound in your first approach. Use the fact that geometric series converge. $\endgroup$ Apr 6 at 17:52
  • $\begingroup$ @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 $\endgroup$
    – JetLeg
    Apr 6 at 17:55
  • $\begingroup$ 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? $\endgroup$
    – JetLeg
    Apr 6 at 17:58
  • $\begingroup$ I didn’t read it deeply enough. $\endgroup$ Apr 6 at 17:58
  • $\begingroup$ @YuvalFilmus Would appreciate your kind help! :) $\endgroup$
    – JetLeg
    Apr 6 at 18:00

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – JetLeg
    Apr 7 at 4:50
  • $\begingroup$ @fastttt, please come here for a chat. $\endgroup$
    – John L.
    Apr 7 at 5:07
  • $\begingroup$ Thank you so much! :) $\endgroup$
    – JetLeg
    Apr 15 at 23:17
  • $\begingroup$ @fastttt You are welcome! $\endgroup$
    – John L.
    Apr 15 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.