1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$). $\endgroup$ – Nathaniel Apr 11 at 21:16
  • $\begingroup$ 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? $\endgroup$ – hazelnut_116 Apr 11 at 21:34
0
$\begingroup$

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.

$\endgroup$

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.