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$
3
  • $\begingroup$ $n \lg n$ seems to be upper bound, but how accurate is it .. $\endgroup$
    – zkutch
    Commented Jan 28, 2021 at 1:19
  • $\begingroup$ Thanks. Also the "while" indentation was a mistake and has been fixed. Thanks for the edit. :) $\endgroup$
    – kasra
    Commented Jan 28, 2021 at 5:40
  • $\begingroup$ Hello @kasra, I thought it would be following $\sum\limits_{k=1}^{n}klg(n-k)$ ? Could you explain this? $\endgroup$ Commented Jan 23 at 6:10

1 Answer 1

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
    Commented Jan 28, 2021 at 5:38

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.