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)$
2 Answers 2
$\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)$
-
$\begingroup$ $\log n! \neq n \log n - n$ $\endgroup$Steven– Steven2024年01月24日 10:30:00 +00:00Commented Jan 24, 2024 at 10:30
-
$\begingroup$ @Steven it is asymptotically equal en.m.wikipedia.org/wiki/Stirling%27s_approximation $\endgroup$Kenneth Kho– Kenneth Kho2024年01月24日 10:39:56 +00:00Commented 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$Steven– Steven2024年01月24日 11:22:34 +00:00Commented 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$Kenneth Kho– Kenneth Kho2024年01月24日 11:48:28 +00:00Commented Jan 24, 2024 at 11:48
-
1$\begingroup$ It works now.$\phantom{}$ $\endgroup$Steven– Steven2024年01月24日 12:23:35 +00:00Commented Jan 24, 2024 at 12:23
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).