1
$\begingroup$

Consider the following algorithm:
(the print operation prints a single asterisk; the operation x = 2x doubles the value of the variable x).

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

Let f (n) be the time complexity of this algorithm (or equivalently the number of times * is printed). Provide correct bounds for O(f (n)) and Ω(f (n)), ideally converging on Θ(f (n)).

This question is one of practices in The Algorithm Design Manuel.

I found the time complexity to be $\sum\limits_{k=1}^{n}\lceil\lg(\frac n k)\rceil$

My question is, could this (or any function) be its own upper and lower bound?

Also is there a way to simplify this function (like writing the sums using some formula like $\frac{n(n+1)}2$)?

Thanks in advance.

$\endgroup$
2
  • $\begingroup$ $n \lg n$ seems to be upper bound, but how accurate is it .. $\endgroup$
    – zkutch
    Jan 28 at 1:19
  • $\begingroup$ Thanks. Also the "while" indentation was a mistake and has been fixed. Thanks for the edit. :) $\endgroup$
    – kasra
    Jan 28 at 5:40
2
$\begingroup$

Ever heard of Stirling's approximation? :) Well, it implies that $(\frac{n}{e})^{n} \leq n! \leq e^2 \cdot (\frac{n}{e})^{n+1}$. We will use it get a nice upper and lower bound on your function:

Upper Bound: $$\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \leq n + \log \frac{n^n}{n!} \leq n + \log (e^n) = O(n)$$

Lower Bound:

$$\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \geq \log \frac{n^n}{n!} \geq \log \Big(\frac{e^{n-1}}{n} \Big) = \log(e^{n-1}) - \log n= \Omega(n) $$


Thus, we get $\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil = \Theta(n) $

$\endgroup$
1
  • $\begingroup$ Thanks very much. :-) $\endgroup$
    – kasra
    Jan 28 at 5:38

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.