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

asked Jan 24, 2024 at 6:07
$\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)$

answered Jan 24, 2024 at 10:15
$\endgroup$
5
  • $\begingroup$ $\log n! \neq n \log n - n$ $\endgroup$ Commented Jan 24, 2024 at 10:30
  • $\begingroup$ @Steven it is asymptotically equal en.m.wikipedia.org/wiki/Stirling%27s_approximation $\endgroup$ Commented Jan 24, 2024 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$ Commented Jan 24, 2024 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$ Commented Jan 24, 2024 at 11:48
  • 1
    $\begingroup$ It works now.$\phantom{}$ $\endgroup$ Commented Jan 24, 2024 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).

answered Jan 24, 2024 at 9:55
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.