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.