1
$\begingroup$

I am trying to find complexity for following algorithm. It is from "The Algorithm Design Manual" book.

for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

I simulated algorithm for some values. Each time inner loop operates on n-k value.

k=1
   x=1
   x=2
   x=4
   x=8
   ...
k=2
   x=2
   x=4
   x=8
   x=16
k=3
   x=3
   x=6
   x=12

And I do think that it has complexity of

$\sum\limits_{k=1}^{n}k*\lg(n-k)$

What do you think?

Edit 1

After some time, I think it should be $\sum\limits_{k=1}^{n}\lg(n-k)$

$\endgroup$

2 Answers 2

2
$\begingroup$

$\sum\limits_{k=1}^{n}\log \frac{n}{k} = \sum\limits_{k=1}^{n}\log n-\sum\limits_{k=1}^{n}\log k = \log n^n - \log n! = n \log n - (n \log n - n + O(\log n)) = n - O(\log n) = O(n)$

$\endgroup$
5
  • $\begingroup$ $\log n! \neq n \log n - n$ $\endgroup$
    – Steven
    Jan 24 at 10:30
  • $\begingroup$ @Steven it is asymptotically equal en.m.wikipedia.org/wiki/Stirling%27s_approximation $\endgroup$ Jan 24 at 10:39
  • $\begingroup$ @Keneth sure it is. But 1) you wrote equal, and 2) it is not legal to subtract asymptotically equal functions. Otherwise your could write: $ n - (n - \log n) = n - (n - \log \log n) = \log \log n$ since $n - \log n$ and $n - \log \log n$ are asymptotically equal. $\endgroup$
    – Steven
    Jan 24 at 11:22
  • $\begingroup$ @Steven is it legal now? i edited it exactly how wikipedia wrote it. being asymptotically equal may not be enough, but they differ only by the ignorable $O(\log n)$. $\endgroup$ Jan 24 at 11:48
  • 1
    $\begingroup$ It works now.$\phantom{}$ $\endgroup$
    – Steven
    Jan 24 at 12:23
1
$\begingroup$

You need to add log (n / k), not log (n - k).

To examine this closer: For values n/2 <= k <= n you have only one iteration of the inner loop. For values n/4 <= k < n/2 you have two iterations. For values n/8 <= k < n/4 you have three iterations of the inner loop.

So the total number of iterations of the inner loop is 1 * n/2 + 2 * n/4 + 3 * n/8 + 4 * n/16 ... which is n + n/2 + n/4 + n/8 ... which is 2n. So you have about 2n iterations in total of the inner loop, and the total time is O(n).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.