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

|cite|improve this question
$\endgroup$
  • $\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$ – skankhunt42 Feb 19 '17 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$ – user3930057 Feb 20 '17 at 3:35
  • 2
    $\begingroup$ It's the number of iterations, but you need the values k. $\endgroup$ – gnasher729 Feb 20 '17 at 13:58
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.

|cite|improve this answer
$\endgroup$
  • $\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$ – user3930057 Feb 21 '17 at 5:45
  • $\begingroup$ @user3930057 Sum of a geometric progression. I omitted the denominator since it is (2-1)=1. $\endgroup$ – quicksort Feb 21 '17 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$ – user3930057 Feb 21 '17 at 9:22
  • $\begingroup$ @user3930057 No. Where does $n$ come from, by the way? $\endgroup$ – quicksort Feb 21 '17 at 9:27
  • $\begingroup$ Sorry, I meant this $$\sum_{h=0}^{\lambda}\lfloor2^{u-h}\rfloor = 2^{u+1}-2^{u-\lambda}$$ $\endgroup$ – user3930057 Feb 21 '17 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).

|cite|improve this answer
$\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.