# Time complexity and upper and lower bounds

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

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

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