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 &lt; 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.
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) $