What is the right solution for this algorithm analysis? I am having a problem from Algorithm Design Manual, this problem want me to provide a $f(n)$ of this code that I can directly use that to calculate the value of $result$. After several tries I come to this solution which does not seem right. Here is the solution.
Code:
Punky(n):
   result = 0;
   for k = 1 to n:
      x = k
      while (x < n):
         result = result + 1
         x = 2 * x;
    
   return result


My Solution:
$$\sum_{i=1}^n lg(n-k+2) = $$
$$n * lg(n) - lg(n!)  + n$$
I believe this is not right as I am not getting my estimation right. What will be right solution for this?
 A: Sometimes it can help to work through loops by trying a few iterations...
Start with $k=1$. Then $x=1$.  While $x < n$:
$\quad \text{result} = 1, x=2$
$\quad \text{result} = 2, x=4$
$\quad \text{result} = 3, x=8$
$\quad \dots$
$\quad \text{result} = \lceil \log_2{n} \rceil, x > n$
Next $k=2$. Then $x=2$.  While $x < n$:
$\quad \text{result} = \text{old result} + 1, x=2 \cdot 2$
$\quad \text{result} = \text{old result} + 2, x=2 \cdot 4$
$\quad \text{result} = \text{old result} + 3, x=2 \cdot 8$
$\quad \dots$
$\quad \text{result} = \text{old result} + \lceil \log_2{(n/2)} \rceil, x > n$
And hopefully you can see that for each $k$ value, the algorithm adds the value $\lceil \log_2{n/k} \rceil$ to the result.  So you're after is
$$\sum_{k = 1}^n{ \lceil \log_2{n/k} \rceil } \tag{1}$$
We can easily get a close estimate for the sum:
$$\sum_{k = 1}^n{ \lceil \log_2{n/k} \rceil } = \sum_{k = 1}^n{ \log_2{(n/k)} } + O(n) \tag{2}$$
Where the $O(n)$ term is just the rounding error, which is at most $n$.
Then the new sum can be expanded, since the logarithms have integers as inputs.
$$\sum_{k = 1}^n{ \log_2{(n/k)} } = \underbrace{\log_2(n)-\log_2(1)}_{k=1} + \underbrace{\log_2(n)-\log_2(2)}_{k=2} + \dots + \underbrace{\log_2(n)-\log_2(n)}_{k=n} \tag{3}$$
We can rewrite or re-group as
$$\sum_{k = 1}^n{ \log_2{(n/k)} } = \sum_{k = 1}^n{ \log{(n/k)} } +O(n) = \sum_{k = 1}^n{ \log{(n)} } - \sum_{k = 1}^n{ \log{(k)} } + O(n) \tag{4}$$
From here, we can rewrite our two sums as products, using this equation from Wikipedia.
$$\prod_k{f(k)} = \exp\left( \sum_k{( \log{f(k)} )} \right) \tag{5}$$
$$\log{ \left( \prod_k{f(k)} \right) } = \sum_k{( \log{f(k)} )} \tag{6}$$
Rewriting our two summands on the right from Equation (4), and using Equation (6) we now have
$$\sum_{k = 1}^n{ \log{(n)} } - \sum_{k = 1}^n{ \log{(k)} } + O(n) = $$
$$\log{ \left( \prod_k{n} \right) } - \log{ \left( \prod_k{k} \right) } + O(n) = $$ $$\log{(n^n)} - \log{(n!)} + O(n) \tag{7}$$
and this is our estimate. We could rewrite this as
$$\log{ \left( n^n / n!\right) } \tag{8}$$
