Time complexity and upper and lower bounds

Question

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.

Answer 1

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