0

I know that this platform is probably not the best place for this question, on stack overflow I didn't receive any answers. Consider the following code snippet:

for (int i = n; i >= 1; i = i / 2) {
    for (int j = 1; j <= i; j = 2 * j) {
        f();
    }
}

We want to determine the number of times f() get's called. My solution: $$ \sum_{i=1}^{\log _{2}(n)} \sum_{j=1}^{\log _{2}(i)} 1 = \sum_{i=1}^{\log _{2}(n)} \log _{2}(i)$$ Apparently the solution is $\Theta(\log^2(n))$, how can I reduce the above further?

Hilberto1
  • 1,046

2 Answers2

1

Your statement is correct but it is not in the form expected for an answer. We usually expect answers like this to be in the form $n^a (\log n)^b$ which makes them easy to compare. As your expression is given it is not clear how it compares with other expressions. It is similar to a problem where the expected answer is $3$ and somebody gives $\frac 62$.

You were expected to notice that you are summing $\log_2 n$ terms, each of which is at most $\log_2 n$, so the total is less than $(\log_2 n)^2$

Ross Millikan
  • 374,822
0

I agree with Ross's answer, the simplest is indeed to bound $$\sum\limits_{i=1}^{\log_2(n)}\log_2(i)\le\sum\limits_{i=1}^{\log_2(n)}\log_2(n)=\Theta(\log_2(n)^2)$$

The sum is not directly calculable but roughly speaking we can invoke the comparison sum and integral.

Take for instance $\sum\limits_{i=1}^n i=\dfrac{n(n+1)}{2}=\Theta(n^2)$ and the integral is $\displaystyle \int_1^n x\,dx=\bigg[\frac 12x^2\bigg]_1^n=\Theta(n^2)$ as well.

Similarly since an antiderivative of the natural logarithm is

$\displaystyle\int_1^{\ln(n)}\ln(x)\,dx=\bigg[x\ln(x)-x\bigg]_1^{\ln(n)}=\Theta\big(\ln(n)\ln(\ln(n))-\ln(n)\big)=\Theta\big(\ln(n)\ln(\ln(n)\big)$

We can expect a result $\Theta\big(\log_2(n)\log_2(\log_2(n))\big)$ for your nested loops, which is a bit lower than $\Theta(\log_2(n)^2)$, but the latter is good enough in first approximation.

zwim
  • 28,563