0
$\begingroup$

r Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term comes from, but I am completley lost on the $3 \ln N$ term. Unfortunatley this is the only solution.

$\endgroup$
  • 1
    $\begingroup$ The factor 3 comes from the fact that it is accessing three times the array $a$ in line 5. $\endgroup$ – Marcelo Fornet Oct 11 at 3:30
4
$\begingroup$

Let's consider the outer two loops first. For a fixed value of $i$, the number of iterations of the middle loop is exactly $n-1 - (i+1) + 1 = n - i -1$. Since $i$ ranges from $0$ to $n-1$ (in the outer loop), the overall number of iterations of the middle loop is: $$ \sum_{i=0}^{n-1} (n - i -1) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}. $$

For each of those iterations we execute the inner loop for a certain number $x \in \mathbb{N}$ of iterations. Notice that $x$ only depends on $n$ and not on $i$ or $j$. Before the first iteration, the value of $k$ is $1$, and it doubles after every iteration (i.e., before the next iteration starts). This means that after a generic number $h \in \mathbb{N}$ of iterations (i.e., just before the $(h+1)$-th iteration starts) the value of $k$ is $2^h$. Since the loop continues as long as $k = 2^h < n$, we are interested in the minimum value of $h$ for which the above inequality is not true. This is $x = \lceil \log n \rceil $ if $n \ge 1$ (where we used the fact that $h$ must be a non-negative integer) and $x = 0$ otherwise. Since you are interested in the asymptotic behavior of the algorithm, I will ignore this latter case.

Finally, notice that for each iteration of the inner loop, exactly $3$ array accesses are performed.

To summarize:

  • We reach the inner loop $\frac{n(n-1)}{2}$ times;
  • Each time we perform $\lceil \log n \rceil$ iterations;
  • Each iteration causes $3$ array accesses.

The total number of array accesses is therefore: $ \frac{3}{2}n(n-1) \lceil \log n \rceil \sim \frac{3}{2}n^2 \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.