2
$\begingroup$

I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :)

Im a computer science student currently taking on Introduction to computer science, we recently learned about Big O and its formal definition. While looking at exercises, me and my friends had problem agreeing on the correct most Precise upper bound for this function

Pseudocode :
Function foo(L is list)
    n = length of L
    Do while n > 0
        n = n floor division over 2
        Do for i=0 upto i=n-1
            Something with complexity of O(1)
        End for
    End while
    return L

Python:
def foo(L:list):
    n = len(lst)
    while n>0:
         n = n//2
         for i in range(n):
             # some O(1) code
    return L

My attempt: So we know that the innermost loop in relative to n at Log(n) - 1 times, then we also know the outer while loop runs Log(n) times.

so that gives us O((Log(n))^2) time complexity

My friend's attempt:

The innermost loop is a simple for loop over n so that is of time complexity of O(n) and the outer most loop runs at Log(n) times which gives us O(nlog(n))

at this point I'm Completely lost , How does the inner loop give us O(n) if its loop times is determined by n which is reduced to half each time ? as in this is not a simple nested loop that loop over the same number of iterations A clarification is much much much appreciated

Happy weekend.

$\endgroup$

3 Answers 3

2
$\begingroup$

Both are wrong.

The inner loop makes $n$ iterations, for $n$ decreasing in a geometric progression. If the initial $N$ is an exact power of $2$, the total is

$$\frac N2+\frac N4+\frac N8+\cdots2+1=N-1.$$


  • you confuse the value of $n$ and the number of times it is halved,

  • they don't take into account the fast decrease of $n$.

$\endgroup$
1
  • $\begingroup$ Oh i understand now , now i feel stupid for not seeing that. Thank you so much :D $\endgroup$
    – David Mos
    Apr 1 at 13:53
1
$\begingroup$

You are both wrong, the correct asnwer is $O(n)$ (and is not very intuitive why).

To clarify, before I explain why this is $O(n)$ - you are right that you friend's attempt is impercise because $n$ changes in the outer 'while' loop.

However, your answer is actually wrong for the exact same reason! You didn't carefully enough fogure how $n$ changes and how that affects the inner loop.

Now, to explain why the overall complexity is $O(n)$: in the first iteration of the outer loop, we "pay" $\dfrac{n}{2}$. In the next iteration, we "pay" $\dfrac{n}{4}$. In the next one, $\dfrac{n}{8}$, and so on.

So, the general formula for the run-time will be:

$$\frac{n}{2}+\frac{n}{4}+...+1\le n\cdot \left(1+\frac{1}{2}+...\right)=n\cdot 2=O(n)$$ Where the last equality is derived as the sum of a geometric series.

$\endgroup$
10
  • $\begingroup$ The first term is $\frac n2$. The OP is not wrong for the same reason as friends. $\endgroup$ Apr 1 at 15:30
  • $\begingroup$ @Yves the first term is indeed $\frac n2$, but it isn't really important when considering the big-O complexity... It just makes the calculations a bit easier. Also, what I meant by "the OP is wrong for the same reason as their friends", is in that they didn't carefully consider the run-time of the inner loop. $\endgroup$
    – nir shahar
    Apr 1 at 15:56
  • 1
    $\begingroup$ What went on my mind is that ive always thought that we always multiply how many times the outer loop iterates with how many times the inner loop iterates, this problem proved a challenge for me because i have never stumbled upon a nested loop in which the inner loop is directly related to the value of n which changes each time we enter the outer loop. This helped understand that not everything is some "Equation" but rather it requires some thinking. in fact after both of you guys's answers i fail to even understand how on earth i had arrived to my original answer. Thanks both <3 $\endgroup$
    – David Mos
    Apr 1 at 23:32
  • 1
    $\begingroup$ So yea i said okay relative to the current size of n before the floor division the inner loop runs log(n) times which is basically n/2 assuming n is a direct power of 2. and the outer loop runs also log(n) times since each time we are halving the length. but the log(n) is basically the number of elements that are included in the addition n/2 + n/4 + ... + 1 , my thought process was all over the place. $\endgroup$
    – David Mos
    Apr 1 at 23:35
  • 1
    $\begingroup$ @nirshahar thanks for the suggestion, an advice from a fellow student at the tel aviv university for computer science is considerably appreciated haha $\endgroup$
    – David Mos
    Apr 5 at 23:39
0
$\begingroup$

Your answer of $O((\log n)^2)$ is incorrect because the cost of each iteration is not $O(\log n)$; for example, the cost of the first iteration is proportional to $n/2$. Your friend’s answer $O(n \log n)$ is correct, but this upper bound is not asymptotically tight. It’s not wrong to say that the total cost is $O(n \log n)$, but $O(n)$ is a better upper bound, and this upper bound is asymptotically tight.

The amount of work done in the first iteration is $n/2$, in the second iteration is $n/4$, etc, and sothe total cost is $\frac{n}{2} + \frac{n}{4} + \cdots = \Theta(n)$.

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