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.

• zkutch: $n \lg n$ seems to be upper bound, but how accurate is it ..
• kasra: Thanks. Also the "while" indentation was a mistake and has been fixed. Thanks for the edit. :)
• nurgasemetey: Hello @kasra, I thought it would be following $\sum\limits_{k=1}^{n}klg(n-k)$ ? Could you explain this?

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

• kasra: Thanks very much. :-)