1
$\begingroup$

So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code:

int sum = 0;
for(int i = 1; i < n; i *= 2) {
    for(int j = n; j > 0; j /= 2) {
        for(int k = j; k < n; k += 2) {
            sum += i + j * k;
        }
    }
}

Now from what I calculated for the loops, first loop runs log(n) times, second loop runs (log(n) * log(n)) times and the third loop is the one which is causing confusion, because I believe it runs for (n - j)/2 times. My question is can I assume it to be n/2 times, because I think it won't be a tight upper bound if I do that. Or is there a different approach that I am missing?

$\endgroup$
  • $\begingroup$ Yes you can because this amount of sloppiness in permissible with asymptotics. $\endgroup$ – Navjot Singh Sep 29 '18 at 15:50
  • $\begingroup$ @Apass.Jack what? $\endgroup$ – Osama Asif C Infinitum Sep 29 '18 at 18:12
  • $\begingroup$ I am writing an answer. Just to tell anybody who wants to write an answer that we might be doing the same work. So she/he can either go ahead or tell me that she is writing an answer. I can then stop writing mine possibly, to save my time. It takes a lot of time to write an answer that is correct, clean and easy to understand. $\endgroup$ – John L. Sep 29 '18 at 18:18
  • $\begingroup$ Got it, thanks for replying, waiting for the answer. $\endgroup$ – Osama Asif C Infinitum Sep 29 '18 at 18:19
0
$\begingroup$

One common way to arrive at a tight big-$O$ upper bound of the complexity of an algorithm is to estimate one. Then prove that estimate works.

Let me take your computation by nested loops as an example.


In this post $\log(x)$ means $\log_2(x)$. The first loop runs $\lceil\log(n)\rceil$ iterations. For each iteration in the first loop, the second loop runs $\lfloor\log(n)\rfloor+1$ iterations. For each iteration in the second loop, the third loop runs $\lfloor(n - j+1)/2\rfloor$ iterations, where $j>0$ is the loop variable of the second loop. Ignoring the floor function, the addition by the constant 1, the subtraction by $j$, the division by the constant 2 and the constant number of operations executed by each iteration in the third loop, I will estimate the upper bound of the number of total operations as $O(\log(n)\log(n)\,n)$.

Is that $O(n\log^2n)$ a tight upper bound of the the number of total operations $T(n)$? Yes, it is indeed.


Firstly, let us show it is an upper bound. We can assume $n>2$. Let $c_3$ be the number of operations executed by each iteration of the third loop. $$ T(n) \le (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor+1)(n/2)c_3\\ \le (2\log(n))(2\log(n))(n/2)c_3\\ \le (2c_3)n\log^2n $$

Now let us show it is tight. Let us do not count the first iteration of the the second loop. That is, let us only consider the operation done by the second loop starting from $j=\lfloor n/2\rfloor$. Then for each iteration in the second loop, the third loop runs $⌊(n−j+1)/2⌋ \ge n/2-1$ iterations. Then for $n\ge6$, $$ T(n) \ge (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor)(n/2-1)c_3\\ \ge (\log(n))(\log(n)/2)(n/3)c_3\\ \ge (c_3/6)n\log^2n\\ $$

So we have proved from the ground up.


The above proof, although rigorous and clear, is not the usual way to reason about the big-$O$ because it is so exact as to require too much thinking. That is almost the kind of computation needed to get the exact asymptotic approximation. Here is a simpler version assuming you are familiar with the big-$\Theta$ notations.

The first loop run $\Theta(\log(n)$ iterations. For each iteration in the first loop, the second loop runs $\Theta(\log(n)$ iterations. For all but the first iteration in the second loop, the third loop runs between $n/2$ to $n$ iterations, which is $\Theta(n)$ iterations. In the first iteration of the second loop, the third loop runs no iteration. So $$T(n)=\Theta(\log(n)(\Theta(\log(n)-1)\Theta(n)=\Theta(\log(n))\Theta(\log(n))\Theta(n)=\Theta(n\log^2(n))$$ which implies $O(n\log^2n)$ is the tight upper bound.


By the way, in all computations above we are not counting the operations to maintains the indice $i,j,k$. That is ignored by convention, because they will not change our approximation in big $O$-notations unless in extraordinary situations. Or because in many situations we are only interested in the number of the "real" operations.

The reasoning about the big-$O$ notations can be an art or a precise process. On the one hand, you can be very "sloppy" when you are trying to get an estimate and even when you are reasoning. That is because you can hide or absorb constant factors into the notations. That way you can arrive at a possible answer very quickly. With practice and experience, you can be certain immediately most of the times once you got an estimate. On the other hand, you can also verify every part of the "sloppy" process by rigorous mathematical deduction or by applying a set of valid shortcut rules. In the end, we will arrive at a precise conclusion using the big-$O$ notations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks alot! A really good answer! Understood it quite clearly! $\endgroup$ – Osama Asif C Infinitum Sep 30 '18 at 4:07
  • $\begingroup$ Did it now, tried before it wasn't working then, but it works now! Thanks! $\endgroup$ – Osama Asif C Infinitum Sep 30 '18 at 4:32
  • $\begingroup$ No problem. Welcome to the site! $\endgroup$ – John L. Sep 30 '18 at 4:33

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.