4
$\begingroup$

I am trying to find out how many times the "statement" is executed by finding its formula based on these loops:

int s = 0;
for(int k = n; k > 0; k /= 2)
{
  for(int l = k; l < n; l++)
  {
    s++; // statement
  }
}

I have been stuck with this problem for a while since I couldn't really get the correct formula whenever I compared the result of my formula to the output s.

I started by doing this:

$$T(n) = \sum_{k=1}^{\left\lfloor{\log_2(n)}\right\rfloor + 1}\sum_{l=k}^{n-1} 1$$

then eventually got this as a result:

$$T(n) = (1/2)(\left\lfloor{\log_2(n)}\right\rfloor + 1)(2n - \left\lfloor{\log_2(n)}\right\rfloor-2)$$

Does anyone know how to solve this kind of problem?

(This is a self-made problem btw since I kind of find analysis of algorithms fun)

$\endgroup$
3
  • $\begingroup$ I don't understand your first summation. Why does k go from 1 to log(n)+1? In the for loop, k goes like n, n/2, n/4, etc. $\endgroup$ Feb 19, 2017 at 17:55
  • $\begingroup$ It can also be k = 0 to log(n). Anyway, what I understood was log(n) denotes the max number of iterations the outer loop performs. $\endgroup$ Feb 20, 2017 at 3:35
  • 2
    $\begingroup$ It's the number of iterations, but you need the values k. $\endgroup$
    – gnasher729
    Feb 20, 2017 at 13:58

2 Answers 2

8
$\begingroup$

We can determine the exact value of $s$ as a function of $n$. For the sake of brevity, let $\lambda = \left \lfloor \lg n \right \rfloor$. We can replace the inner loop with:

$s \leftarrow s+n-k$

At the end of the program we'll have:

$$ s= \sum_{h=0}^{\lambda} n - \left \lfloor \frac{n}{2^h} \right \rfloor = n \left( \lambda + 1 \right) - \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor $$

Our problem is now rewriting the last term in a nicer form. . Certainly $n$ has a unique representation in base $2$, in particular it is true that

$$ n = \sum_{u \in S} 2^u $$

for some $S \subseteq \mathbb{N}_{\le \lambda}$.

Therefore we have:

$$ \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor = \sum_{h=0}^{\lambda} \sum_{u \in S} \left \lfloor 2^{u-h} \right \rfloor = \sum_{u \in S} \sum_{h=0}^{\lambda} \left \lfloor 2^{u-h} \right \rfloor = \sum_{u \in S} 2^{u+1} -1 $$

But then:

$$ \sum_{u \in S} 2^{u+1} -1 = 2n - |S| $$

Piercing it all together, at the end of the program we will have:

$$ s = n \left ( \left \lfloor \lg n \right \rfloor - 1\right) + \textbf{1}(n) $$

where $\textbf{1}(n)$ is the Hamming norm of $n$, that is, the number of ones in its binary representation.

$\endgroup$
6
  • $\begingroup$ How did this happen? $$\sum_{u\in S}\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = \sum_{u\in S}2^{u+1}-1$$ $\endgroup$ Feb 21, 2017 at 5:45
  • $\begingroup$ @user3930057 Sum of a geometric progression. I omitted the denominator since it is (2-1)=1. $\endgroup$
    – quicksort
    Feb 21, 2017 at 9:01
  • $\begingroup$ Using sum of geometric progression, doesn't it become like this?$$\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = 2^{u+1}-2^{u-n}$$ $\endgroup$ Feb 21, 2017 at 9:22
  • $\begingroup$ @user3930057 No. Where does $n$ come from, by the way? $\endgroup$
    – quicksort
    Feb 21, 2017 at 9:27
  • $\begingroup$ Sorry, I meant this $$\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = 2^{u+1}-2^{u-\lambda}$$ $\endgroup$ Feb 21, 2017 at 9:29
1
$\begingroup$

The outer loop runs about log n times.

The inner loop runs 0 times during the first iteration when k = n. All the other times, 0 ≤ k ≤ n/2, so the inner loop runs between n/2 and n times, so we have O (n log 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.